Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA14-03501S" target="_blank" >GA14-03501S: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Mathematical and Engineering Methods in Computer Science, Lecture Notes in Computer Science 9548

ISBN

9783319298160

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

54-66

Název nakladatele

Springer

Místo vydání

Switzerland

Místo konání akce

Telč

Datum konání akce

23. 10. 2015

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

000374173700006