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.
|