Parametrized Complexity of Length-Bounded Cuts and Multi-cuts

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Parametrized Complexity of Length-Bounded Cuts and Multi-cuts
Original language description
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).
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

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

Article name in the collection
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
—
Number of pages
12
Pages from-to
441-452
Publisher name
SPRINGER-VERLAG BERLIN
Place of publication
BERLIN
Event location
Singapore
Event date
May 18, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000361755700037

Similar results(10)