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

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

doi:10.1007/11561927_21

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

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

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

59 Citations (Scopus)

145 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 language	Undefined
Title of host publication	Distributed Computing: 19th International Conference, DISC 2005
Editors	Pierre Fraigniaud
Place of Publication	Berlin
Publisher	Springer
Pages	273-283
Number of pages	15
ISBN (Print)	3-540-29163-6
DOIs	https://doi.org/10.1007/11561927_21
Publication status	Published - Nov 2005
Event	Distributed Computing: 19th International Conference, DISC 2005 - Cracow, Poland Duration: 26 Sept 2005 → 29 Sept 2005

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer-Verlag
Volume	3724
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Distributed Computing: 19th International Conference, DISC 2005
Period	26/09/05 → 29/09/05
Other	26-29 Sep 2005

Keywords

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

Access to Document

10.1007/11561927_21

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). Springer. https://doi.org/10.1007/11561927_21

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

}

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., 10.1007/11561927_21, Lecture Notes in Computer Science, vol. 3724, Springer, Berlin, pp. 273-283, Distributed Computing: 19th International Conference, DISC 2005, 26/09/05. https://doi.org/10.1007/11561927_21

Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. / Kuhn, Fabian; Moscibroda, Thomas; Nieberg, T. et al.
Distributed Computing: 19th International Conference, DISC 2005. ed. / Pierre Fraigniaud. Berlin: Springer, 2005. p. 273-283 10.1007/11561927_21 (Lecture Notes in Computer Science; Vol. 3724).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Kuhn, Fabian

AU - Moscibroda, Thomas

AU - Nieberg, T.

AU - Wattenhofer, Roger

PY - 2005/11

Y1 - 2005/11

N2 - 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.

AB - 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.

KW - EC Grant Agreement nr.: FP6/004400

KW - EWI-1686

KW - METIS-226109

KW - IR-65538

U2 - 10.1007/11561927_21

DO - 10.1007/11561927_21

M3 - Conference contribution

SN - 3-540-29163-6

T3 - Lecture Notes in Computer Science

SP - 273

EP - 283

BT - Distributed Computing: 19th International Conference, DISC 2005

A2 - Fraigniaud, Pierre

PB - Springer

CY - Berlin

T2 - Distributed Computing: 19th International Conference, DISC 2005

Y2 - 26 September 2005 through 29 September 2005

ER -