On the Complexity of Distributed Greedy Coloring

DOI10.1007/978-3-540-75142-7_37MaRDI QIDQ3523231zbMATH OpenOpenAlexFDO

Authors Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Alfredo Navarra

Publication date 2 September 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-75142-7_37

Mathematics Subject Classification ID

Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• On the complexity of distributed graph coloring with local minimality constraints
• On the complexity of distributed graph coloring
• Distributed maximal matching, greedy is optimal
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds

Cited in

(7)

• Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge
• Distributed algorithms for fractional coloring
• On the complexity of distributed graph coloring with local minimality constraints
• Message passing for the coloring problem: Gallager meets Alon and Kahale
• scientific article; zbMATH DE number 6850477 (Why is no real title available?)
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• Distributed Coloring in Sparse Graphs with Fewer Colors

This page was built for publication: On the Complexity of Distributed Greedy Coloring

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