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
Další údaje
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
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
Klíčová slova anglicky
multiway cut; matroid circuit; cocircuit
Příznaky
Mezinárodní význam, Recenzováno
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