Cover Image

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhattacharya, Sayan, Carmon, Din, Costa, Martín, Solomon, Shay, Zhang, Tianyi
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
by: Bhattacharya, Sayan, et al.
Published: (2024)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
by: Bukov, Anton, et al.
Published: (2023)

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, et al.
Published: (2025)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2026)

Faster Dynamic $(Δ+1)$-Coloring Against Adaptive Adversaries
by: Flin, Maxime, et al.
Published: (2025)

A Lossless Deamortization for Dynamic Greedy Set Cover
by: Solomon, Shay, et al.
Published: (2024)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
by: Elkin, Michael, et al.
Published: (2024)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
by: Boneh, Itai, et al.
Published: (2025)

Faster Deterministic Streaming Vertex Coloring
by: Chechik, Shiri, et al.
Published: (2026)

$(Δ+ 1)$ Vertex Coloring in $O(n)$ Communication
by: Flin, Maxime, et al.
Published: (2024)

Faster Edge Coloring by Partition Sieving
by: Akmal, Shyan, et al.
Published: (2025)

Improved Streaming Edge Coloring
by: Chechik, Shiri, et al.
Published: (2025)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
by: Dhawan, Abhishek
Published: (2024)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
by: Bhattacharya, Sayan, et al.
Published: (2023)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
by: Assadi, Sepehr
Published: (2024)

Dynamic Set Cover with Worst-Case Recourse
by: Solomon, Shay, et al.
Published: (2025)

Dynamic $(Δ+ 1)$ Vertex Coloring
by: Benson-Tilsen, Noam
Published: (2026)

Streaming Edge Coloring with Subquadratic Palette Size
by: Chechik, Shiri, et al.
Published: (2023)

Approximate Light Spanners in Planar Graphs
by: Le, Hung, et al.
Published: (2025)

Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $Ω(\log n)$ Lightness Barrier
by: Le, Hung, et al.
Published: (2023)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
by: Bhattacharya, Sayan, et al.
Published: (2025)

Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut
by: Baswana, Surender, et al.
Published: (2025)

Faster Algorithms for Dual-Failure Replacement Paths
by: Chechik, Shiri, et al.
Published: (2024)

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
by: Bodwin, Greg, et al.
Published: (2023)

Beyond Brooks: $(Δ-1)$-Coloring in Semi-Streaming
by: Flin, Maxime, et al.
Published: (2026)

Faster Distributed $Δ$-Coloring via Ruling Subgraphs
by: Bourreau, Yann, et al.
Published: (2025)

Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors
by: Wang, Yulin, et al.
Published: (2023)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
by: Behnezhad, Soheil, et al.
Published: (2024)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
by: Bernstein, Aaron, et al.
Published: (2025)

Breaking the Barrier of Self-Concordant Barriers: Faster Interior Point Methods for M-Matrices
by: Vladu, Adrian
Published: (2025)

Faster Distributed $Δ$-Coloring via a Reduction to MIS
by: Bourreau, Yann, et al.
Published: (2025)

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths
by: Atalig, Sunny, et al.
Published: (2025)

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time
by: Kowalik, Lukasz
Published: (2024)