Excluded minors, network decomposition, and multicommodity flow

DOI10.1145/167088.167261zbMath1310.90017OpenAlexW2042899161MaRDI QIDQ5248539

Satish B. Rao, Philip N. Klein, Serge A. Plotkin

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.167261

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Flows in graphs (05C21)

Related Items (57)

Absolute Lipschitz extendability ⋮ Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation ⋮ A note on multiflows and treewidth ⋮ Asymptotic dimension of planes and planar graphs ⋮ An improved approximation ratio for the minimum linear arrangement problem ⋮ An approximate max-flow min-cut relation for undirected multicommodity flow, with applications ⋮ Improved bounds on the max-flow min-cut ratio for multicommodity flows ⋮ Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem ⋮ Markov type and threshold embeddings ⋮ Covering metric spaces by few trees ⋮ Metric decompositions of path-separable graphs ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ Strong-diameter decompositions of minor free graphs ⋮ The all-or-nothing flow problem in directed graphs with symmetric demand pairs ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ Unnamed Item ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees ⋮ Unnamed Item ⋮ Graph Clustering using Effective Resistance ⋮ Metric uniformization and spectral bounds for graphs ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover ⋮ Advances in metric embedding theory ⋮ Partition-based logical reasoning for first-order and propositional theories ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow ⋮ On average distortion of embedding metrics into the line ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Comparison of Metric Spectral Gaps ⋮ New graph decompositions with applications to emulations ⋮ Linearity of grid minors in treewidth with applications through bidimensionality ⋮ Space-efficient path-reporting approximate distance oracles ⋮ The intrinsic dimensionality of graphs ⋮ Sparse covers for planar graphs and graphs that exclude a fixed minor ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ Extending Lipschitz functions via random metric partitions ⋮ Unnamed Item ⋮ Correlation clustering in general weighted graphs ⋮ Randomly removing \(g\) handles at once ⋮ A tight bound on approximating arbitrary metrics by tree metrics ⋮ Quasimetric embeddings and their applications ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ A node-capacitated Okamura-Seymour theorem ⋮ Local embeddings of metric spaces ⋮ Covering Metric Spaces by Few Trees ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs ⋮ Conformal growth rates and spectral geometry on distributional limits of graphs ⋮ Planar graphs: Random walks and bipartiteness testing ⋮ Separators in region intersection graphs ⋮ Cutting Corners Cheaply, or How to Remove Steiner Points ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ Integer plane multiflow maximisation: one-quarter-approximation and gaps ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Balanced partitions of trees and applications ⋮ On approximating planar metrics by tree metrics.

This page was built for publication: Excluded minors, network decomposition, and multicommodity flow