Campus Units

Electrical and Computer Engineering, Computer Science

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

7-2014

Journal or Book Title

Algorithmica

Volume

69

Issue

3

First Page

658

Last Page

684

DOI

10.1007/s00453-013-9757-4

Abstract

We consider the construction of sparse covers for planar graphs and other graphs that exclude a fixed minor. We present an algorithm that gives a cover for the γ-neighborhood of each node. For planar graphs, the cover has radius less than 16γ and degree no more than 18. For every n node graph that excludes a minor of a fixed size, we present an algorithm that yields a cover with radius no more than 4γ and degree O(logn).

This is a significant improvement over previous results for planar graphs and for graphs excluding a fixed minor; in order to obtain clusters with radius O(γ), it was required to have the degree polynomial in n. Our algorithms are based on a recursive application of a basic routine called shortest-path clustering, which seems to be a novel approach to the construction of sparse covers.

Since sparse covers have many applications in distributed computing, including compact routing, distributed directories, synchronizers, and Universal TSP, our improved cover construction results in improved algorithms for all these problems, for the class of graphs that exclude a fixed minor.

Comments

This is a manuscript of an article published as Busch, Costas, Ryan LaFortune, and Srikanta Tirthapura. "Sparse Covers for Planar Graphs and Graphs that Exclude a Fixed Minor." Algorithmica 69, no. 3 (2014): 658-684. The final publication is available at Springer via DOI: 10.1007/s00453-013-9757-4. Posted with permission.

Copyright Owner

Springer Science+Business Media New York

Language

en

File Format

application/pdf

Published Version

Share

COinS