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


Share/Save/Bookmark

Kuhn, Fabian and Moscibroda, Thomas and Nieberg, Tim and Wattenhofer, Roger (2005) Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. In: 19th International Conference on Distributed Computing, DISC 2005, 26-29 September 2005, Cracow, Poland (pp. pp. 273-283).

open access
[img]
Preview
PDF
276kB
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.
Item Type:Conference or Workshop Item
Copyright:© 2005 Springer
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65538
Official URL:http://dx.doi.org/10.1007/11561927_21
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 226109