scientific article; zbMATH DE number 7758343

DOI10.4230/lipics.approx/random.2020.41MaRDI QIDQ6084397

Eden Chlamtáč, Petr Kolman

Publication date: 31 October 2023

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

approximation algorithmscut-flow dualitylength bounded cutsrounding of linear programms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• On the hardness of approximating minimum vertex cover
• Interdiction problems on planar graphs
• Mengerian theorems for paths of bounded length
• Finding the most vital arcs in a network
• On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
• Parametrized Complexity of Length-Bounded Cuts and Multi-cuts
• Length-bounded cuts and flows
• Fractals for Kernelization Lower Bounds
• On Algorithms Employing Treewidth for $L$-bounded Cut Problems
• Improved Hardness for Cut, Interdiction, and Firefighter Problems