Deterministic distributed vertex coloring in polylogarithmic time

DOI10.1145/1835698.1835797zbMath1315.68198OpenAlexW2007218972MaRDI QIDQ5176216

Leonid Barenboim, Michael Elkin

Publication date: 2 March 2015

Published in: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.590.5207

zbMATH Keywords

arboricityarbdefective-coloringpartial-orientation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (12)

A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Can we locally compute sparse connected subgraphs? ⋮ Symmetry breaking depending on the chromatic number or the neighborhood growth ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ Multipath Spanners via Fault-Tolerant Spanners ⋮ Combinatorial algorithms for distributed graph coloring ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ Trading Bit, Message, and Time Complexity of Distributed Algorithms ⋮ Combinatorial Algorithms for Distributed Graph Coloring ⋮ Locality and Checkability in Wait-Free Computing

Uses Software

• CCSTM

Cites Work

• Elastic Transactions
• Toward a theory of transactional contention managers
• Software transactional memory

This page was built for publication: Deterministic distributed vertex coloring in polylogarithmic time