Approximate max-flow min-(multi)cut theorems and their applications

DOI10.1145/167088.167266zbMath1310.05198OpenAlexW2117319425MaRDI QIDQ5248541

Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Flows in graphs (05C21)

Related Items (27)

A Mixed Integer Model for the Sparsest Cut problem ⋮ Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems ⋮ An approximate max-flow min-cut relation for undirected multicommodity flow, with applications ⋮ The geometry of graphs and some of its algorithmic applications ⋮ Primal-dual approximation algorithms for feedback problems in planar graphs ⋮ Improved bounds on the max-flow min-cut ratio for multicommodity flows ⋮ Stabilizing Network Bargaining Games by Blocking Players ⋮ A derandomized approximation algorithm for the critical node detection problem ⋮ A randomized algorithm with local search for containment of pandemic disease spread ⋮ A Region Growing Algorithm for Detecting Critical Nodes ⋮ Approximating minimum feedback sets and multi-cuts in directed graphs ⋮ Nonlinear formulations and improved randomized approximation algorithms for multicut problems ⋮ Approximation algorithms for feasible cut and multicut problems ⋮ Scheduling multicasts on unit-capacity trees and meshes. ⋮ Computation in Causal Graphs ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover ⋮ Multiway cuts in directed and node weighted graphs ⋮ Advances in metric embedding theory ⋮ 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 ⋮ Colocating tasks in data centers using a side-effects performance model ⋮ The ferry cover problem ⋮ Polynomial time approximation schemes for dense instances of minimum constraint satisfaction ⋮ Correlation clustering in data streams ⋮ Stabilizing network bargaining games by blocking players ⋮ A simple algorithm for the multiway cut problem ⋮ A penalty function heuristic for the resource constrained shortest path problem

This page was built for publication: Approximate max-flow min-(multi)cut theorems and their applications