Parametrized Complexity of Length-Bounded Cuts and Multi-cuts
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10312398" target="_blank" >RIV/00216208:11320/15:10312398 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-319-17142-5_37" target="_blank" >http://dx.doi.org/10.1007/978-3-319-17142-5_37</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-17142-5_37" target="_blank" >10.1007/978-3-319-17142-5_37</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Parametrized Complexity of Length-Bounded Cuts and Multi-cuts
Popis výsledku v původním jazyce
We show that the minimal length-bounded L-cut can be computed in linear time with respect to L and the tree-width of the input graph as parameters. We derive an FPT algorithm for a more general multi-commodity length bounded cut problem when parameterized by the number of terminals also. For the former problem we show a W[1]-hardness result when the parameterization is done by the path-width only (instead of the tree-width).
Název v anglickém jazyce
Parametrized Complexity of Length-Bounded Cuts and Multi-cuts
Popis výsledku anglicky
We show that the minimal length-bounded L-cut can be computed in linear time with respect to L and the tree-width of the input graph as parameters. We derive an FPT algorithm for a more general multi-commodity length bounded cut problem when parameterized by the number of terminals also. For the former problem we show a W[1]-hardness result when the parameterization is done by the path-width only (instead of the tree-width).
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2015
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015), Lecture Notes in Computer Science
ISBN
978-3-319-17141-8
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
12
Strana od-do
441-452
Název nakladatele
SPRINGER-VERLAG BERLIN
Místo vydání
BERLIN
Místo konání akce
Singapore
Datum konání akce
18. 5. 2015
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000361755700037