Strong-diameter decompositions of minor free graphs

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and 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(r 6rρ) and the probability an edge (u,v) is cut is O(r \, d(u,v)/ρ).

Details

Publication typeInproceedings
Published inACM Symposium on Parallel Algorithms and Architectures (SPAA)
Pages16-24
ISBN978-1-59593-667-7
AddressSan Diego, California
PublisherACM
> Publications > Strong-diameter decompositions of minor free graphs