@inproceedings{86945f653f2c42edaa8a393ef6e39f9f,

title = "Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs",

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.",

keywords = "EC Grant Agreement nr.: FP6/004400, EWI-1686, METIS-226109, IR-65538",

author = "Fabian Kuhn and Thomas Moscibroda and T. Nieberg and Roger Wattenhofer",

year = "2005",

month = nov,

doi = "10.1007/11561927_21",

language = "Undefined",

isbn = "3-540-29163-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "273--283",

editor = "Pierre Fraigniaud",

booktitle = "Distributed Computing: 19th International Conference, DISC 2005",

note = "Distributed Computing: 19th International Conference, DISC 2005 ; Conference date: 26-09-2005 Through 29-09-2005",

}