Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Embeddings:
TR08-060 | 10th April 2008
James R. Lee, Prasad Raghavendra

Coarse Differentiation and Multi-flows in Planar Graphs

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 by Chakrabarti.et.al 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 ... more >>>

ISSN 1433-8092 | Imprint