Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs

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, 2016, p. 54-66. ISBN 978-3-319-29816-0. Available from: https://dx.doi.org/10.1007/978-3-319-29817-7_6.

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

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

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

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

---

Abstract

V originále

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.

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 project	Name: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky Investor: Czech Science Foundation
MUNI/A/1159/2014, interní kód MU	Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IV. Investor: Masaryk University, Category A