Polynomial lower bound for distributed graph coloring in a weak LOCAL model

DOI10.1007/978-3-662-53426-7_8zbMath1393.68184arXiv1607.05212OpenAlexW2487364517MaRDI QIDQ1660925

Angelika Steger, Dan Hefetz, Yannic Maus, Fabian Kuhn

Publication date: 16 August 2018

Full work available at URL: https://arxiv.org/abs/1607.05212

zbMATH Keywords

lower boundcolor reductiondistributed graph coloringdistributed symmetry breakingLOCAL modelneighborhood graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Related Items (2)

A Time Hierarchy Theorem for the LOCAL Model ⋮ Linial for lists

This page was built for publication: Polynomial lower bound for distributed graph coloring in a weak LOCAL model