scientific article; zbMATH DE number 7758343

DOI10.4230/LIPICS.APPROX/RANDOM.2020.41MaRDI QIDQ6084397zbMATH OpenFDO

Authors Eden Chlamtac, Petr Kolman

Publication date 31 October 2023

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2020.41

zbMATH Keywords

approximation algorithmscut-flow dualitylength bounded cutsrounding of linear programms

Mathematics Subject Classification ID

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

Cites work

• A refined complexity analysis of finding the most vital edges for undirected shortest paths
• Finding the most vital arcs in a network
• Fractals for kernelization lower bounds
• Graph theory with applications
• scientific article; zbMATH DE number 3353312 (Why is no real title available?)
• Improved hardness for cut, interdiction, and firefighter problems
• Interdiction problems on planar graphs
• Length-bounded cuts and flows
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Mengerian theorems for paths of bounded length
• On algorithms employing treewidth for L-bounded cut problems
• On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow
• On the hardness of approximating minimum vertex cover
• Parametrized complexity of length-bounded cuts and multi-cuts
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(2)

• Length-bounded cuts: proper interval graphs and structural parameters
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast

This page was built for publication:

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