A fast distributed algorithm for \((\Delta+1)\)-edge-coloring

DOI10.1016/j.jctb.2021.10.004zbMath1485.05048arXiv2006.15703OpenAlexW3208522216MaRDI QIDQ2664558

Anton Bernshteyn

Publication date: 17 November 2021

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.15703

zbMATH Keywords

edge-coloringdistributed algorithmsLOCAL modelhappy edgeshopeful chainsmulti-step Vizing's algorithmsuccessful chains

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (2)

On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Linial for lists

Cites Work

• Measurable versions of Vizing's theorem
• Graph Theory
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Parallel Symmetry-Breaking in Sparse Graphs
• Locality in Distributed Graph Algorithms
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Towards the locality of Vizing’s theorem
• Deterministic distributed edge-coloring with fewer colors
• Unnamed Item
• Unnamed Item

This page was built for publication: A fast distributed algorithm for \((\Delta+1)\)-edge-coloring