Strong Diameter Decompositions
of Minor Free Graphs
Cyril Gavoille Dahlia Malkhi Udi Wieder |
Abstract We provide the first sparse covers and
probabilistic partitions for graphs excluding a fixed minor that have strong diameter
bounds; i.e. each set of the cover/partition has a small diameter as an
induced sub-graph. Using these results we provide improved distributed name-independent
routing schemes. Specifically, given a graph excluding a minor on r vertices
and a parameter ρ > 0 we obtain the flowing results: (1) a polynomial
algorithm that constructs a set of clusters such that each cluster has a
strong-diameter of O(r2 ρ) and each vertex belongs to 2O(r)r!
clusters; (2) a name-independent routing scheme with
a stretch of O(r2) and tables of size 2O(r)r! log4
n bits; (3) a randomized algorithm that partitions the graph such that each
cluster has strong-diameter O(r6r ρ) and the probability an
edge (u, v) is cut is O(r d(u, v)/ρ). |
|
[SPAA 07 version pdf] |
||
|