Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

DOI10.1145/331524.331526zbMath1065.68666OpenAlexW2150148016WikidataQ56030327 ScholiaQ56030327MaRDI QIDQ3158558

No author found.

Publication date: 25 January 2005

Published in: Journal of the ACM (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (only showing first 100 items - show all)

On the Max-flow min-cut ratio for directed multicommodity flows ⋮ Efficient reassembling of graphs. I: The linear case ⋮ Crossing number, pair-crossing number, and expansion ⋮ On Cutwidth Parameterized by Vertex Cover ⋮ Single-commodity robust network design with finite and hose demand sets ⋮ A note on multiflows and treewidth ⋮ Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems ⋮ Feedback arc set problem in bipartite tournaments ⋮ Approximation algorithms for treewidth ⋮ \(\ell ^2_2\) spreading metrics for vertex ordering problems ⋮ Approximation algorithms for requirement cut on graphs ⋮ Vertical perimeter versus horizontal perimeter ⋮ Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem ⋮ EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS ⋮ Flow metrics ⋮ Terminal embeddings ⋮ Unbalanced graph partitioning ⋮ Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing ⋮ Congestion-Free Rerouting of Flows on DAGs ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ Graph Bisection with Pareto Optimization ⋮ General variable neighborhood search for computing graph separators ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ Metric decompositions of path-separable graphs ⋮ The multi-multiway cut problem ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Scheduling series-parallel task graphs to minimize peak memory ⋮ The all-or-nothing flow problem in directed graphs with symmetric demand pairs ⋮ Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\) ⋮ \(N\)-fold integer programming and nonlinear multi-transshipment ⋮ Approximating the Rectilinear Crossing Number ⋮ Unnamed Item ⋮ A polyhedral study of lifted multicuts ⋮ Euclidean prize-collecting Steiner forest ⋮ Approximation algorithms via contraction decomposition ⋮ Expander graphs and their applications ⋮ On the expansion and diameter of bluetooth-like topologies ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Corner cuts are close to optimal: from solid grids to polygons and back ⋮ Single-Sink Multicommodity Flow with Side Constraints ⋮ Pathwidth, trees, and random embeddings ⋮ Solving the maximum duo-preservation string mapping problem with linear programming ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ Rerouting Flows when Links Fail ⋮ Unnamed Item ⋮ \(d\)-dimensional arrangement revisited ⋮ A bottleneck detection algorithm for complex product assembly line based on maximum operation capacity ⋮ Sparsest cuts and concurrent flows in product graphs. ⋮ On treewidth approximations. ⋮ Algorithms for the universal and a priori TSP ⋮ Cutwidth: obstructions and algorithmic aspects ⋮ On cutwidth parameterized by vertex cover ⋮ Approximation algorithms for digraph width parameters ⋮ Bounds on maximum concurrent flow in random bipartite graphs ⋮ Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery ⋮ The Complexity Status of Problems Related to Sparsest Cuts ⋮ The Small Set Vertex expansion problem ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ A queueing network-based distributed Laplacian solver ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Lower bounds for in-network computation of arbitrary functions ⋮ Polynomiality of sparsest cuts with fixed number of sources ⋮ Lattice flows in networks ⋮ Most balanced minimum cuts ⋮ On certain connectivity properties of the internet topology ⋮ Electric routing and concurrent flow cutting ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ Meet and merge: approximation algorithms for confluent flows ⋮ Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem ⋮ Unnamed Item ⋮ Correlation clustering in general weighted graphs ⋮ A Separator Theorem for String Graphs and its Applications ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem ⋮ Inoculation strategies for victims of viruses and the sum-of-squares partition problem ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ A simple algorithm for the multiway cut problem ⋮ On the complexity of finding balanced oneway cuts ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions ⋮ Graph Clustering in All Parameter Regimes ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ Communities, Random Walks, and Social Sybil Defense ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ Separators in region intersection graphs ⋮ Network coding in undirected graphs is either very helpful or not helpful at all ⋮ An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut ⋮ Approximating the rectilinear crossing number ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs ⋮ Separator-based graph embedding into multidimensional grids with small edge-congestion ⋮ Balanced partitions of trees and applications ⋮ Linear time algorithms for finding sparsest cuts in various graph classes ⋮ Metric-Constrained Optimization for Graph Clustering Algorithms ⋮ Braess's paradox in expanders

This page was built for publication: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms