Reference
Schneider, J., & Wattenhofer, R. (2010). An Optimal Maximal Independent Set Algorithm for Bounded-Independence Graphs. Journal of Distributed Computing, 15(1), 15-26.
Publication type
Article in Scientific Journal
Abstract
We present a novel distributed algorithm for the maximal independent set (MIS) problem. On bounded-independence graphs (BIG) our deterministic algorithm ?nishes in O(log* n) time, n being the number of nodes. In light of Linial’s Omega(log* n) lower bound our algorithm is asymptotically optimal. Furthermore, it solves the con- nected 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 and a maximal matching 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