Pathwidth, trees, and random embeddings |
| |
Authors: | James R. Lee Anastasios Sidiropoulos |
| |
Affiliation: | 1. Computer Science & Engineering, University of Washington, Washington, USA 2. Toyota Technological Institute at Chicago, Chicago, USA
|
| |
Abstract: | We prove that, for every integer k≥1, every shortest-path metric on a graph of pathwidth k embeds into a distribution over random trees with distortion at most c=c(k), independent of the graph size. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair [12] states that for every minor-closed family of graphs F, there is a constant c(F) such that the multi-commodity max-flow/min-cut gap for every flow instance on a graph from F is at most c(F). The preceding embedding theorem is used to prove this conjecture whenever the family F does not contain all trees. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|