Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on



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

Faculty of Informatics

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: