Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1316745,
author = {Hliněný, Petr and Slámečka, Ondřej},
address = {Switzerland},
booktitle = {Mathematical and Engineering Methods in Computer Science, Lecture Notes in Computer Science 9548},
doi = {http://dx.doi.org/10.1007/978-3-319-29817-7_6},
editor = {Jan Kofroň, Tomáš Vojnar},
keywords = {multiway cut; matroid circuit; cocircuit},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Switzerland},
isbn = {978-3-319-29816-0},
pages = {54-66},
publisher = {Springer},
title = {Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs},
year = {2016}
}
TY - JOUR
ID - 1316745
AU - Hliněný, Petr - Slámečka, Ondřej
PY - 2016
TI - Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs
PB - Springer
CY - Switzerland
SN - 9783319298160
KW - multiway cut
KW - matroid circuit
KW - cocircuit
N2 - 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.
ER -
HLINĚNÝ, Petr a Ondřej SLÁMEČKA. Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs. In Jan Kofroň, Tomáš Vojnar. \textit{Mathematical and Engineering Methods in Computer Science, Lecture Notes in Computer Science 9548}. Switzerland: Springer, 2016, s.~54-66. ISBN~978-3-319-29816-0. Dostupné z: https://dx.doi.org/10.1007/978-3-319-29817-7\_{}6.
|
