Parametrized Complexity of Length-Bounded Cuts and Multi-cuts

DOI10.1007/978-3-319-17142-5_37zbMath1454.68056OpenAlexW2262201633WikidataQ57937811 ScholiaQ57937811MaRDI QIDQ2948489

Pavel Dvořák, Dušan Knop

Publication date: 30 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-17142-5_37

zbMATH Keywords

parameterized algorithmslength-bounded cutsW[1-hardness]

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (6)

On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow ⋮ Fractals for Kernelization Lower Bounds ⋮ Unnamed Item ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ Parameterized complexity of length-bounded cuts and multicuts

This page was built for publication: Parametrized Complexity of Length-Bounded Cuts and Multi-cuts