Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs

Fabian Kuhn, Thomas Moscibroda, T. Nieberg, Roger Wattenhofer

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

47 Citations (Scopus)
47 Downloads (Pure)

Abstract

Abstract. The distributed complexity of computing a maximal independent set in a graph is of both practical and theoretical importance. While there exists an elegant O(log n) time randomized algorithm for general graphs, no deterministic polylogarithmic algorithm is known. In this paper, we study the problem in graphs with bounded growth, an important family of graphs which includes the well-known unit disk graph and many variants thereof. Particularly, we propose a deterministic algorithm that computes a maximal independent set in time O(logΔ·log n) in graphs with bounded growth, where n and Δ denote the number of nodes and the maximal degree in G, respectively.
Original languageUndefined
Title of host publicationDistributed Computing: 19th International Conference, DISC 2005
EditorsPierre Fraigniaud
Place of PublicationBerlin
PublisherSpringer
Pages273-283
Number of pages15
ISBN (Print)3-540-29163-6
DOIs
Publication statusPublished - Nov 2005

Publication series

NameLecture Notes in Computer Science
PublisherSpringer-Verlag
Volume3724
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • EC Grant Agreement nr.: FP6/004400
  • EWI-1686
  • METIS-226109
  • IR-65538

Cite this

Kuhn, F., Moscibroda, T., Nieberg, T., & Wattenhofer, R. (2005). Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. In P. Fraigniaud (Ed.), Distributed Computing: 19th International Conference, DISC 2005 (pp. 273-283). [10.1007/11561927_21] (Lecture Notes in Computer Science; Vol. 3724). Berlin: Springer. https://doi.org/10.1007/11561927_21