On Algorithms Employing Treewidth for $L$-bounded Cut Problems
From MaRDI portal
Publication:4637663
DOI10.7155/jgaa.00462zbMath1384.05147arXiv1705.02390OpenAlexW2790988318MaRDI QIDQ4637663
Publication date: 25 April 2018
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1705.02390
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (6)
Length-bounded cuts: proper interval graphs and structural parameters ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Graph minors. III. Planar tree-width
- Extended formulation for CSP that is compact for instances of bounded treewidth
- On short paths interdiction problems: Total and node-wise limited interdiction
- Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
- Mengerian theorems for paths of bounded length
- Treewidth. Computations and approximations
- Diameter and treewidth in minor-closed graph families
- Finding the most vital arcs in a network
- Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
- Parametrized Complexity of Length-Bounded Cuts and Multi-cuts
- Undirected single-source shortest paths with positive integer weights in linear time
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Length-bounded cuts and flows
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems
- Improved Hardness for Cut, Interdiction, and Firefighter Problems
- Parameterized Algorithms
- Faster shortest-path algorithms for planar graphs
- On the complexity of \(k\)-SAT
This page was built for publication: On Algorithms Employing Treewidth for $L$-bounded Cut Problems
