Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs

Investor logo

Warning

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

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

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

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:

You are running an old browser version. We recommend updating your browser to its latest version.