Fast randomized algorithms for distributed edge coloring

DOI10.1145/135419.135465zbMath1369.68346OpenAlexW1977820641MaRDI QIDQ5348856

Aravind Srinivasan, Alessandro Panconesi

Publication date: 21 August 2017

Published in: Proceedings of the eleventh annual ACM symposium on Principles of distributed computing - PODC '92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/135419.135465

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

Neighborhood graphs and distributed Δ+1-coloring ⋮ Exploiting storage redundancy to speed up randomized shared memory simulations ⋮ (Probabilistic) recurrence relations revisited ⋮ Symmetry breaking depending on the chromatic number or the neighborhood growth ⋮ Distributed strong diameter network decomposition ⋮ Probabilistic recurrence relations revisited ⋮ Partitioning into degenerate graphs in linear time ⋮ Near-optimal distributed edge coloring ⋮ Link scheduling in wireless sensor networks: distributed edge-coloring revisited ⋮ Complete convergence of weighted sums under negative dependence ⋮ Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory ⋮ A lower bound for communication on the crossbar ⋮ Unnamed Item ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set