Strong-diameter decompositions of minor free graphs

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

June 2007

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:

- A polynomial algorithm that constructs a set of clusters such that each cluster has a strong-diameter of
*O(r*and each vertex belongs to^{2}ρ)*2*clusters;^{O(r)}r! - A name-independent routing scheme with a stretch of
*O(r*and tables of size^{2})*2*bits; (3) a randomized algorithm that partitions the graph such that each cluster has strong-diameter^{O(r)}r! log^{4}n*O(r 6*and the probability an edge^{r}ρ)*(u,v)*is cut is*O(r \, d(u,v)/ρ)*.

Publication type | Inproceedings |

Published in | ACM Symposium on Parallel Algorithms and Architectures (SPAA) |

Pages | 16-24 |

ISBN | 978-1-59593-667-7 |

Address | San Diego, California |

Publisher | ACM |

> Publications > Strong-diameter decompositions of minor free graphs