Fulltext

An optimal maximal independent setalgorithm for bounded-independence graphs

Schneider, Johannes ; Wattenhofer, Roger

In: Distributed Computing, 2010, vol. 22, no. 5-6, p. 349-361

Add to personal list
    Title
    • An optimal maximal independent setalgorithm for bounded-independence graphs
    Author
    • Schneider, Johannes. Computer Engineering and Networks Laboratory, ETH Zurich, 8092, Zurich, Switzerland
    • Wattenhofer, Roger. Computer Engineering and Networks Laboratory, ETH Zurich, 8092, Zurich, Switzerland
    Document Type
    • Postprint
    OAI-PMH Identifier
    • oai:doc.rero.ch:314131
    Summary
    We present a novel distributed algorithm for the maximal independent set problem (This is an extended journal version of Schneider and Wattenhofer in Twenty-seventh annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, 2008). On bounded-independence graphs our deterministic algorithm finishes in O(log* n) time, n being the number of nodes. In light of Linial's Ω(log* n) lower bound our algorithm is asymptotically optimal. Furthermore, it solves the connected dominating set problem for unit disk graphs in O(log* n) time, exponentially faster than the state-of-the-art algorithm. With a new extension our algorithm also computes a δ+1 coloring and a maximal matching in O(log* n) time, where δ is the maximum degree of the graph