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
Paper in Conference Proceedings
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