We provide the first sparse covers and probabilistic partitions for graphs excluding a fixed minor that have \emph{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 $\rho > 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(r^2 \rho)$ and each vertex belongs to $2^{O(r)}r!$ clusters;

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

PDF file

In: ACM Symposium on Parallel Algorithms and Architectures (SPAA)

Publisher: ACM

Details