@inproceedings{0eecde9d2b7446c0a777d603d2c13fde,
title = "Polynomial lower bound for distributed graph coloring in a weak LOCAL model",
abstract = "We show an Ω(formula presented) lower bound on the runtime of any deterministic distributed O(Δ1+η)-graph coloring algorithm in a weak variant of the LOCAL model. In particular, given a network graph G = (V,E), in the weak LOCAL model nodes communicate in synchronous rounds and they can use unbounded local computation. The nodes have no identifiers, but instead, the computation starts with an initial valid vertex coloring. A node can broadcast a single message of unbounded size to its neighbors and receives the set of messages sent to it by its neighbors. The proof uses neighborhood graphs and improves their understanding in general such that it might help towards finding a lower (runtime) bound for distributed graph coloring in the standard LOCAL model.",
keywords = "Color reduction, Distributed graph coloring, Distributed symmetry breaking, LOCAL model, Lower bound, Neighborhood graphs",
author = "Dan Hefetz and Fabian Kuhn and Yannic Maus and Angelika Steger",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2016.; 30th International Symposium on Distributed Computing, DISC 2016 ; Conference date: 27-09-2016 Through 29-09-2016",
year = "2016",
doi = "10.1007/978-3-662-53426-7\_8",
language = "אנגלית",
isbn = "9783662534250",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "99--113",
editor = "Cyril Gavoille and David Ilcinkas",
booktitle = "Distributed Computing - 30th International Symposium, DISC 2016, Proceedings",
}