Approximate max-integral-flow/min-multicut theorems

DOI10.1145/1007352.1007433MaRDI QIDQ3581010zbMATH OpenOpenAlexFDO

Authors Kenji Obata

Publication date 15 August 2010

Published in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Improved approximations for the minimum-cut ratio and the flux
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• Approximating directed multicuts
• Improved bounds on the max-flow min-cut ratio for multicommodity flows

Cited in

(24)

• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• Models and methods for solving the problem of network vulnerability
• Integer plane multiflow maximisation: one-quarter-approximation and gaps
• The max-flow min-cut property and \(\pm 1\)-resistant sets
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
• scientific article; zbMATH DE number 45022 (Why is no real title available?)
• scientific article; zbMATH DE number 176498 (Why is no real title available?)
• Flows, cuts and integral routing in graphs -- an approximation algorithmist's perspective
• Conditional Lower Bounds for All-Pairs Max-Flow
• Improved approximations for the minimum-cut ratio and the flux
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
• Streaming Lower Bounds for Approximating MAX-CUT
• A measure-theoretical max-flow-min-cut problem
• Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• Minimal multicut and maximal integer multiflow: a survey
• Multicommodity flows in tree-like networks
• A note on multiflows and treewidth
• Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity
• Disjoint paths in sparse graphs

This page was built for publication: Approximate max-integral-flow/min-multicut theorems

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