Deterministic distributed edge-coloring via hypergraph maximal matching

DOI10.1109/FOCS.2017.25MaRDI QIDQ6946363zbMATH OpenFDO

Authors Fabian Kuhn, Mohsen Ghaffari, Manuela Fischer

Publication date 6 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2017.25

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(9)

• Local distributed rounding: generalized to MIS, matching, set cover, and beyond
• Fast algorithms for Vizing's theorem on bounded degree graphs
• Brief announcement: Simpler and more general distributed coloring based on simple list defective coloring algorithms
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Locally computing edge orientations
• Local density and its distributed approximation
• Distributed edge coloring in time polylogarithmic in \({\Delta }\)
• Vizing's theorem in near-linear time
• Improved streaming edge coloring

This page was built for publication: Deterministic distributed edge-coloring via hypergraph maximal matching

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