Nearly optimal distributed edge coloring in O(log log n) rounds

DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1098-2418(199705)10:3<385::AID-RSA6>3.0.CO;2-S" /><385::AID-RSA6>3.0.CO;2-S 10.1002/(SICI)1098-2418(199705)10:3<385::AID-RSA6>3.0.CO;2-SzbMath0876.05087OpenAlexW2082903339MaRDI QIDQ4344228

David A. Grable, Alessandro Panconesi

Publication date: 15 July 1997

Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199705)10:3<385::aid-rsa6>3.0.co;2-s

zbMATH Keywords

complexityedge coloringrandomized algorithmsequential algorithm

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)

Related Items (7)

Distributed edge coloration for bipartite networks ⋮ A self-stabilizing \((\Delta +4)\)-edge-coloring algorithm for planar graphs in anonymous uniform systems ⋮ Distance edge coloring and collision‐free communication in wireless sensor networks ⋮ Link scheduling in wireless sensor networks: distributed edge-coloring revisited ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Distributed deterministic edge coloring using bounded neighborhood independence

This page was built for publication: Nearly optimal distributed edge coloring in O(log log n) rounds