You are here:
Publication details
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: |