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

DOI10.1145/3564246.3585150MaRDI QIDQ6499306FDOQ6499306

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

Publication date: 8 May 2024

zbMATH Keywords

approximation algorithmmax-flow min-multicut theoremsmall diameter decomposition

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)