Improved distributed degree splitting and edge coloring

DOI10.4230/LIPICS.DISC.2017.19zbMATH Open1515.68369MaRDI QIDQ6487490FDOQ6487490

Authors: Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, Jara Uitto 

Publication date: 3 February 2023

Recommendations

• Improved distributed degree splitting and edge coloring
• Distributed degree splitting, edge coloring, and orientations
• Deterministic distributed edge-coloring with fewer colors
• \((2\Delta-1)\)-edge-coloring is much easier than maximal matching in the distributed setting
• Towards the locality of Vizing's theorem

zbMATH Keywords

discrepancyedge coloringdistributed graph algorithmsdegree splitting

Mathematics Subject Classification ID

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

Cited In (3)

• Improved distributed degree splitting and edge coloring
• Classification of distributed binary labeling problems
• Distributed degree splitting, edge coloring, and orientations

This page was built for publication: Improved distributed degree splitting and edge coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6487490)