Paths of bounded length and their cuts: parameterized complexity and algorithms
From MaRDI portal
Publication:456699
DOI10.1016/J.DISOPT.2010.09.009zbMATH Open1248.90071OpenAlexW2050719228MaRDI QIDQ456699FDOQ456699
Authors: Petr A. Golovach, Dimitrios M. Thilikos 
Publication date: 16 October 2012
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2010.09.009
Recommendations
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Parameterized complexity of length-bounded cuts and multicuts
- Parametrized complexity of length-bounded cuts and multi-cuts
- Two edge-disjoint paths with length constraints
- Finding two edge-disjoint paths with length constraints
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Maximal Flow Through a Network
- On problems without polynomial kernels
- The directed subgraph homeomorphism problem
- Graph minors. XIII: The disjoint paths problem
- Easy problems for tree-decomposable graphs
- Color-coding
- Title not available (Why is that?)
- The complexity of finding two disjoint paths with min-max objective function
- On the complexity of vertex-disjoint length-restricted path problems
- Heuristics for finding a maximum number of disjoint bounded paths
- The complexity of finding maximum disjoint paths with length constraints
- A special planar satisfiability problem and a consequence of its NP- completeness
- On the parameterized complexity of multiple-interval graph problems
- Title not available (Why is that?)
- On the Computational Complexity of Combinatorial Problems
- Algorithmic lower bounds for problems parameterized by clique-width
- Mengerian theorems for paths of bounded length
- Length-Bounded Cuts and Flows
- Length-bounded cuts and flows
- Capacitated Domination and Covering: A Parameterized Perspective
- Planar capacitated dominating set is \(W[1]\)-hard
- On miniaturized problems in parameterized complexity theory
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
- On line disjoint paths of bounded length
- A linear-time algorithm for edge-disjoint paths in planar graphs
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- Title not available (Why is that?)
- Improved bounds for the unsplittable flow problem
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (28)
- Two edge-disjoint paths with length constraints
- Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs
- On the complexity of finding internally vertex-disjoint long directed paths
- A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints
- A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
- The complexity of finding small separators in temporal graphs
- Snapshot disjointness in temporal graphs
- On the length of simplex paths: The assignment case
- Title not available (Why is that?)
- On algorithms employing treewidth for \(L\)-bounded cut problems
- Parameterized complexity of length-bounded cuts and multicuts
- Parametrized complexity of length-bounded cuts and multi-cuts
- A survey of parameterized algorithms and the complexity of edge modification
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Confronting intractability via parameters
- On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow
- A constraint programming approach to the additional relay placement problem in wireless sensor networks
- Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
- Multistage \(s-t\) path: confronting similarity with dissimilarity
- Finding two edge-disjoint paths with length constraints
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- Finding disjoint paths on edge-colored graphs: a multivariate complexity analysis
- Title not available (Why is that?)
- Length-bounded cuts: proper interval graphs and structural parameters
- Fractals for kernelization lower bounds
- Title not available (Why is that?)
- An FPT 2-approximation for tree-cut decomposition
- The complexity of finding small separators in temporal graphs
This page was built for publication: Paths of bounded length and their cuts: parameterized complexity and algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456699)
