Local coordination and symmetry breaking

zbMATH Open1409.68324MaRDI QIDQ4967178FDOQ4967178

Authors: Jukka Suomela 

Publication date: 3 July 2019

Full work available at URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/326/308

Recommendations

• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• Linear-in-delta lower bounds in the LOCAL model
• Linear-in-\(\varDelta \) lower bounds in the LOCAL model
• The locality of distributed symmetry breaking
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Cited In (1)

• Linear-in-\(\varDelta \) lower bounds in the LOCAL model

This page was built for publication: Local coordination and symmetry breaking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4967178)