Strong-Diameter Decompositions of Minor Free Graphs

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder

2010

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

following 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), headers of

O(log n+r log r) bits, and tables of size 2O(r)r! log4 n/ log log 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)/ρ).

Publication type | Article |

Published in | Theory of Computing Systems |

Volume | 47 |

Number | 4 |

Publisher | Springer Verlag |

> Publications > Strong-Diameter Decompositions of Minor Free Graphs