Approximate max-flow min-multicut theorem for graphs of bounded treewidth

DOI10.1145/3564246.3585150MaRDI QIDQ6499306zbMATH OpenFDO

Authors Tobias Friedrich, Davis Issac, N. Kumar, Nadym Mallek

Publication date 8 May 2024

Full work available at URL https://doi.org/10.1145/3564246.3585150

zbMATH Keywords

approximation algorithmmax-flow min-multicut theoremsmall diameter decomposition

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• Excluded minors, network decomposition, and multicommodity flow
• Improved approximation algorithms for minimum-weight vertex separators
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• Multi-Commodity Network Flows
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
• The design of approximation algorithms

Cited in

(2)

• Optimal padded decomposition for bounded treewidth graphs
• Improved lower bounds on multiflow-multicut gaps

This page was built for publication: Approximate max-flow min-multicut theorem for graphs of bounded treewidth

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