HLINĚNÝ, Petr and Ondřej SLÁMEČKA. Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs. In Jan Kofroň, Tomáš Vojnar. Mathematical and Engineering Methods in Computer Science, Lecture Notes in Computer Science 9548. Switzerland: Springer. p. 54-66. ISBN 978-3-319-29816-0. doi:10.1007/978-3-319-29817-7_6. 2016.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs
Authors HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution) and Ondřej SLÁMEČKA (203 Czech Republic, belonging to the institution).
Edition Switzerland, Mathematical and Engineering Methods in Computer Science, Lecture Notes in Computer Science 9548, p. 54-66, 13 pp. 2016.
Publisher Springer
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form printed version "print"
Impact factor Impact factor: 0.402 in 2005
RIV identification code RIV/00216224:14330/16:00087736
Organization unit Faculty of Informatics
ISBN 978-3-319-29816-0
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-319-29817-7_6
UT WoS 000374173700006
Keywords in English multiway cut; matroid circuit; cocircuit
Tags formela-conference
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 27/4/2017 00:33.
Abstract
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.
Abstract (in Czech)
Navrhujeme nový algoritmus pro prakticky použitelné generování všech malých vícesměrných řezů v daném grafu, založený na matroidových myšlenkách.
Links
GA14-03501S, research and development projectName: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
Investor: Czech Science Foundation
MUNI/A/1159/2014, interní kód MUName: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IV.
Investor: Masaryk University, Category A
PrintDisplayed: 29/3/2024 02:09