Coarse differentiation and multi-flows in planar graphs

Details Coarse differentiation and multi-flows in planar graphs Coarse differentiation and multi-flows in planar graphs

2008-04-09

arxiv.org/abs/0804.1573v4

Mathematics

Metric Geometry

15 pages, 2 figures; added additional bibliographic information

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Coarse differentiation and multi-flows in planar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Coarse differentiation and multi-flows in planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coarse differentiation and multi-flows in planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-355124