Parametrized complexity of length-bounded cuts and multi-cuts

DOI10.1007/978-3-319-17142-5_37MaRDI QIDQ2948489zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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)

Recommendations

• Parameterized complexity of length-bounded cuts and multicuts
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Length-bounded cuts: proper interval graphs and structural parameters
• The minimum \(k\)-way cut of bounded size is fixed-parameter tractable

Cited in

(16)

• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
• Length-Bounded Cuts and Flows
• Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
• Graph and string parameters: connections between pathwidth, cutwidth and the locality number
• On algorithms employing treewidth for \(L\)-bounded cut problems
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Parameterized complexity of length-bounded cuts and multicuts
• Length-bounded cuts and flows
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Simple and improved parameterized algorithms for multiterminal cuts
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow
• scientific article; zbMATH DE number 7758343 (Why is no real title available?)
• Fractals for kernelization lower bounds
• An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem

This page was built for publication: Parametrized complexity of length-bounded cuts and multi-cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2948489)