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

DOI10.1145/331524.331526zbMATH Open1065.68666DBLPjournals/jacm/LeightonR99OpenAlexW2150148016WikidataQ56030327 ScholiaQ56030327MaRDI QIDQ3158558FDOQ3158558

Authors:

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

Recommendations

• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• Approximate max-integral-flow/min-multicut theorems
• Improved bounds on the max-flow min-cut ratio for multicommodity flows
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Computing and Combinatorics
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• Approximation and Online Algorithms
• Minimal multicut and maximal integer multiflow: a survey

Mathematics Subject Classification ID

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

Cited In (only showing first 100 items - show all)

• Routing in undirected graphs with constant congestion
• Linear time algorithms for finding sparsest cuts in various graph classes
• Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\)
• A note on multiflows and treewidth
• Correlation clustering in general weighted graphs
• Most balanced minimum cuts
• On the complexity of finding balanced oneway cuts
• A decentralized algorithm for spectral analysis
• Approximate duality of multicommodity multiroute flows and cuts: single source case
• Approximation algorithms and hardness of the \(k\)-route cut problem
• Minimal multicut and maximal integer multiflow: a survey
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• Inoculation strategies for victims of viruses and the sum-of-squares partition problem
• Electric routing and concurrent flow cutting
• The complexity status of problems related to sparsest cuts
• Approximation algorithms for treewidth
• Euclidean distortion and the sparsest cut
• Single-commodity robust network design with finite and hose demand sets
• Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems
• On the Max-flow min-cut ratio for directed multicommodity flows
• Algorithms for the universal and a priori TSP
• On algorithms employing treewidth for \(L\)-bounded cut problems
• Flow metrics
• Graph Clustering in All Parameter Regimes
• Feedback arc set problem in bipartite tournaments
• Structural routability of \(n\)-pairs information networks
• The complexity of finding uniform sparsest cuts in various graph classes
• EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS
• Crossing number, pair-crossing number, and expansion
• Approximation algorithms for Euler genus and related problems
• Pathwidth, trees, and random embeddings
• Fast approximation algorithms for multicommodity flow problems
• On certain connectivity properties of the internet topology
• Approximation algorithms for requirement cut on graphs
• A separator theorem for string graphs and its applications
• The multi-multiway cut problem
• Multicommodity flow approximation used for exact graph partitioning
• Advances in metric embedding theory
• \(\ell ^2_2\) spreading metrics for vertex ordering problems
• Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• The all-or-nothing flow problem in directed graphs with symmetric demand pairs
• A polyhedral study of lifted multicuts
• Approximation algorithms for digraph width parameters
• \(N\)-fold integer programming and nonlinear multi-transshipment
• Lattice flows in networks
• Sparsest cuts and concurrent flows in product graphs.
• Structure of graphs with locally restricted crossings
• On cutwidth parameterized by vertex cover
• Approximation algorithms via contraction decomposition
• On cutwidth parameterized by vertex cover
• On treewidth approximations.
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• Efficient reassembling of graphs. I: The linear case
• An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
• The maximum congested cut problem and its robust counterpart: Exact and approximation algorithms for the single and the multicommodity case
• Title not available (Why is that?)
• Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions
• Expander graphs and their applications
• Unbalanced graph partitioning
• Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing
• Computing and Combinatorics
• Solving the maximum duo-preservation string mapping problem with linear programming
• A New Min‐Cut Max‐Flow Ratio for Multicommodity Flows
• Algorithms – ESA 2005
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• Metric-Constrained Optimization for Graph Clustering Algorithms
• Corner cuts are close to optimal: from solid grids to polygons and back
• Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
• Title not available (Why is that?)
• Fast balanced partitioning is hard even on grids and trees
• Balanced partitions of trees and applications
• Multicommodity network flows: a survey. I: Applications and formulations
• On the cover time of dense graphs
• Iterated multilevel simulated annealing for large-scale graph conductance minimization
• Separators in region intersection graphs
• Cutwidth: obstructions and algorithmic aspects
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Single-Sink Multicommodity Flow with Side Constraints
• Congestion-free rerouting of flows on DAGs
• \(d\)-dimensional arrangement revisited
• A simple algorithm for the multiway cut problem
• Rerouting Flows when Links Fail
• A GENERAL PRAM SIMULATION SCHEME FOR CLUSTERED MACHINES
• Bounds on maximum concurrent flow in random bipartite graphs
• Separator-based graph embedding into multidimensional grids with small edge-congestion
• Approximating the rectilinear crossing number
• Braess's paradox in expanders
• Hallucination helps: energy efficient virtual circuit routing
• Network coding in undirected graphs is either very helpful or not helpful at all
• Max-flow min-cut theorem in quantum computing
• On the Parameterized Complexity of Clique Elimination Distance
• Simplex partitioning via exponential clocks and the multiway-cut problem
• The small set vertex expansion problem
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Simulation-based system reliability estimation of a multi-state flow network for all possible demand levels
• Approximating the rectilinear crossing number
• Vertical perimeter versus horizontal perimeter
• Constant congestion routing of symmetric demands in planar directed graphs

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

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