Improved distributed degree splitting and edge coloring

DOI10.4230/LIPICS.DISC.2017.19MaRDI QIDQ6487490zbMATH OpenFDO

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

Publication date 3 February 2023

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)

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

Cited in

(3)

• Classification of distributed binary labeling problems
• Improved distributed degree splitting and edge coloring
• 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)