Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs

HLINĚNÝ, Petr a 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, s. 54-66. ISBN 978-3-319-29816-0. Dostupné z: https://doi.org/10.1007/978-3-319-29817-7_6.

Základní údaje

Originální název

Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs

Autoři

HLINĚNÝ, Petr ORCID a Ondřej SLÁMEČKA

Vydání

Switzerland, Mathematical and Engineering Methods in Computer Science, Lecture Notes in Computer Science 9548, od s. 54-66, 13 s. 2016

Nakladatel

Springer

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/16:00087736

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-29816-0

ISSN

DOI

https://doi.org/10.1007/978-3-319-29817-7_6

UT WoS

000374173700006

EID Scopus

2-s2.0-84975690646

Klíčová slova anglicky

multiway cut; matroid circuit; cocircuit

Štítky

formela-conference

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

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.

Česky

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.

---

Návaznosti

GA14-03501S, projekt VaV	Název: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky Investor: Grantová agentura ČR, Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
MUNI/A/1159/2014, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IV. Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IV., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty