Yuval Emek
ABSTRACT
In [6] it is shown that every graph can be probabilistically embedded into a distribution over its spanning trees with expected distortion O(log2 n log log n), narrowing the gap left by [1], where a lower bound of Ω(log n) is established. This lower bound holds even for the class of series-parallel graphs as proved in [8]. In this paper we close this gap for series-parallel graphs, namely we prove that every n-vertex series-parallel graph can be probabilistically embedded into a distribution over its spanning trees with expected stretch O(log n) for every two vertices. We gain our upper bound 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 series-parallel graph G, whose communication cost is at most O(log n) times larger than that of G.
Index Terms
- A tight upper bound on the probabilistic embedding of series-parallel graphs
Recommendations
A Tight Upper Bound on the Probabilistic Embedding of Series-Parallel Graphs
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 ...
b-coloring of tight graphs
A coloring c of a graph G=(V,E) is a b-coloring if in every color class there is a vertex whose neighborhood intersects every other color class. The b-chromatic number of G, denoted @g"b(G), is the greatest integer k such that G admits a b-coloring with ...
A Tight Upper Bound on Acquaintance Time of Graphs
In this note we confirm a conjecture raised by Benjamini et al. (SIAM J Discrete Math 28(2):767---785, 2014) on the acquaintance time of graphs, proving that for all graphs G with n vertices it holds that $$\mathcal {AC}(G) = O(n^{3/2})$$AC(G)=O(n3/2). ...
Comments