D 2016

Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs

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

Základní údaje

Originální název

Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs

Autoři

HLINĚNÝ, Petr (203 Česká republika, garant, domácí) a Ondřej SLÁMEČKA (203 Česká republika, domácí)

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

Kód RIV

RIV/00216224:14330/16:00087736

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-29816-0

ISSN

DOI

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

UT WoS

000374173700006

Klíčová slova anglicky

multiway cut; matroid circuit; cocircuit

Štítky

formela-conference

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 27. 4. 2017 00:33, RNDr. Pavel Šmerk, Ph.D.

Anotace

ORIG CZ

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
Zobrazeno: 28. 10. 2024 16:13