Constant-Time Dynamic Edge Coloring via Dynamic Splitting and LLL
cs.DS
Submitted: 2026-11-04
Updated: 2026-11-04
Terminology
Sources
- Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time
- A linear-time algorithm for $(1+\epsilon)\Delta$-edge-coloring
- Fully Dynamic $(\Delta+1)$-Coloring in Constant Update Time
- Distributed Edge Coloring with Small Palettes and a Special Case of the Constructive Lov'asz Local Lemma
- Deterministic Simple $(\Delta+\varepsilon\alpha)$-Edge-Coloring in Near-Linear Time
- Dynamic Graph Coloring: Sequential, Parallel, and Distributed
- Fast Distributed Vertex Splitting with Applications
- Dynamic Construction of the Lov'asz Local Lemma
- Constant-Time Dynamic $(\Delta+1)$-Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing
- Fully Dynamic Maximal Matching in Constant Update Time
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time