Name
Abstract | ||
|---|---|---|
We prove that every unweighted series-parallel graph can be probabilistically embedded into its spanning trees with logarithmic distortion. This is tight due to an $\Omega(\log n)$ lower bound established by Gupta, Newman, Rabinovich, and Sinclair on the distortion required to probabilistically embed the $n$-vertex diamond graph into a collection of dominating trees. Our upper bound is gained by presenting a polynomial time probabilistic algorithm that constructs spanning trees with low expected stretch. This probabilistic algorithm can be derandomized to yield a deterministic polynomial time algorithm for constructing a spanning tree of a given (unweighted) series-parallel graph $G$, whose communication cost is at most $O(\log n)$ times larger than that of $G$. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/090745441 | SIAM Journal on Discrete Mathematics |
Keywords | Field | DocType |
series-parallel graphs,probabilistic algorithm,log n,deterministic polynomial time algorithm,probabilistic embedding,polynomial time probabilistic algorithm,logarithmic distortion,communication cost,low expected stretch,series-parallel graph,tight upper bound,vertex diamond graph,unweighted series-parallel graph,lower bound,spanning trees,polynomial time,spanning tree,upper bound | Discrete mathematics,Randomized algorithm,Combinatorics,Embedding,Diamond graph,Upper and lower bounds,Vertex (graph theory),Spanning tree,Probabilistic logic,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
23 | 4 | 0895-4801 |
ISBN | Citations | PageRank |
0-89871-605-5 | 6 | 0.81 |
References | Authors | |
20 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuval Emek | 1 | 440 | 38.14 |
| David Peleg | 2 | 6662 | 824.19 |