Publication details

Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs

Authors

HLINĚNÝ Petr SLÁMEČKA Ondřej

Type Article in Proceedings
Conference Mathematical and Engineering Methods in Computer Science, Lecture Notes in Computer Science 9548
MU Faculty or unit

Faculty of Informatics

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: