Skip to content. | Skip to navigation

Personal tools

Sections
back to overview

A Log-Star Distributed Maximal Independent Set Algorithm for Growth-Bounded Graphs

Reference

Schneider, J., & Wattenhofer, R. (2008). A Log-Star Distributed Maximal Independent Set Algorithm for Growth-Bounded Graphs. Paper presented at the Principles of Distributed Computing (PODC).

Publication type

Refereed Conference Paper

Abstract

We present a novel distributed algorithm for the maximal independent set (MIS) problem. On growth-bounded graphs (GBG) our deterministic algorithm ?nishes in O(log* n) time, n being the number of nodes. In light of Linial’s ?(log* n) lower bound our algorithm is asymp- totically optimal. Our algorithm answers prominent open problems in the ad hoc/sensor network domain. For instance, 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 Delta + 1 coloring in O(log* n) time, where Delta is the maximum degree of the graph

Persons

Organizational Units

  • Institute of Information Systems
  • Hilti Chair of Business Process Management