Skip to content. | Skip to navigation

Personal tools

Sections
back to overview

An Optimal Maximal Independent Set Algorithm for Bounded-Independence Graphs

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

Refereed Journal Article

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