Coarse Differentiation and Multi-flows in Planar Graphs

DOI10.1007/978-3-540-74208-1_17MaRDI QIDQ3603468zbMATH OpenOpenAlexFDO

Authors James R. Lee, Prasad Raghavendra

Publication date 17 February 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0804.1573

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Distance in graphs (05C12)

Abstract: We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound Chakrabarti, Jaffe, Lee, and Vincent for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair. This also improves the largest known gap for planar graphs from 3/2 to 2, yielding the first lower bound that doesn't follow from elementary calculations. Our approach uses the {em coarse differentiation} method of Eskin, Fisher, and Whyte in order to lower bound the distortion for embedding a particular family of shortest-path metrics into $L_1$.

Recommendations

• Coarse differentiation and multi-flows in planar graphs
• Flow-Cut Gaps and Face Covers in Planar Graphs
• On constant multi-commodity flow-cut gaps for families of directed minor-free graphs
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• Improved bounds on the max-flow min-cut ratio for multicommodity flows

Cited in

(2)

• Coarse differentiation and multi-flows in planar graphs
• Potentials in Undirected Graphs and Planar Multiflows

This page was built for publication: Coarse Differentiation and Multi-flows in Planar Graphs

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