Strongly-Bounded Sparse Decompositions of Minor Free Graphs

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

Abstract

As networks grow large and complex, a key approach in managing information and constructing algorithms is to decompose the network into locality-preserving clusters. Then, information and/or management can be divided between the clusters, such that every node is responsible only for clusters for which it belongs. Such decompositions into locality sensitive clusters have become key tools in network and graph theory and span a large body of literature. A key property of a useful decomposition is that each cluster has a short diameter. This property comes in two variants: a weak short diameter in which the short path between nodes may leave the common cluster and a strong diameter, in which each cluster has a small diameter when considered as an induced sub-graph. In this work we present sparse covers and sparse partitions with a bounded strong diameter for the family of minor-free graphs. The tools we present are useful in a large variety of distributed applications such as compact routing and synchronizers.

Details

Publication typeTechReport
NumberMSR-TR-2006-192
Pages0
InstitutionMicrosoft Research
> Publications > Strongly-Bounded Sparse Decompositions of Minor Free Graphs