Deterministic distributed vertex coloring in polylogarithmic time
From MaRDI portal
Publication:5176216
DOI10.1145/1835698.1835797zbMath1315.68198MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
68W15: Distributed algorithms
Related Items
Multipath Spanners via Fault-Tolerant Spanners, Network Decomposition and Distributed Derandomization (Invited Paper), Distributed deterministic edge coloring using bounded neighborhood independence, Symmetry breaking depending on the chromatic number or the neighborhood growth, A fast network-decomposition algorithm and its applications to constant-time distributed computation, Combinatorial algorithms for distributed graph coloring, Can we locally compute sparse connected subgraphs?, Toward more localized local algorithms: removing assumptions concerning global knowledge, Trading Bit, Message, and Time Complexity of Distributed Algorithms, Combinatorial Algorithms for Distributed Graph Coloring, Locality and Checkability in Wait-Free Computing, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation
Uses Software
Cites Work
