Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F16%3A00087736" target="_blank" >RIV/00216224:14330/16:00087736 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-319-29817-7_6" target="_blank" >http://dx.doi.org/10.1007/978-3-319-29817-7_6</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-29817-7_6" target="_blank" >10.1007/978-3-319-29817-7_6</a>
Alternative languages
Result language
angličtina
Original language name
Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs
Original language 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA14-03501S" target="_blank" >GA14-03501S: Parameterized algorithms and kernelization in the context of discrete mathematics and logic</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Mathematical and Engineering Methods in Computer Science, Lecture Notes in Computer Science 9548
ISBN
9783319298160
ISSN
0302-9743
e-ISSN
—
Number of pages
13
Pages from-to
54-66
Publisher name
Springer
Place of publication
Switzerland
Event location
Telč
Event date
Oct 23, 2015
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
000374173700006