Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs
| Authors | |
|---|---|
| Year of publication | 2016 |
| Type | Article in Proceedings |
| Conference | Mathematical and Engineering Methods in Computer Science, Lecture Notes in Computer Science 9548 |
| MU Faculty or unit | |
| Citation | |
| Doi | http://dx.doi.org/10.1007/978-3-319-29817-7_6 |
| Field | Informatics |
| Keywords | multiway cut; matroid circuit; cocircuit |
| Description | We propose a new algorithm for practically feasible exhaustive generation of small multiway cuts in sparse graphs. The purpose of the algorithm is to support a complete analysis of critical combinations of road disruptions in real-world road networks. Our algorithm elaborates on a simple underlying idea from matroid theory – that a circuit-cocircuit intersection cannot have cardinality one (here cocircuits are the generated cuts). We evaluate the practical performance of the algorithm on real-world road networks, and propose algorithmic improvements based on the technique of generation by a canonical construction path. |
| Related projects: |