Buchumschlag

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bhattacharya, Sayan, Costa, Martín, Panski, Nadav, Solomon, Shay
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Arboricity-Dependent Algorithms for Edge Coloring
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

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

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Vizing's Theorem in Near-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

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

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

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

Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
von: Dhawan, Abhishek
Veröffentlicht: (2024)

Dynamic Set Cover with Worst-Case Recourse
von: Solomon, Shay, et al.
Veröffentlicht: (2025)

Dynamic $(Δ+ 1)$ Vertex Coloring
von: Benson-Tilsen, Noam
Veröffentlicht: (2026)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Beyond Brooks: $(Δ-1)$-Coloring in Semi-Streaming
von: Flin, Maxime, et al.
Veröffentlicht: (2026)

$(Δ+ 1)$ Vertex Coloring in $O(n)$ Communication
von: Flin, Maxime, et al.
Veröffentlicht: (2024)

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

A Lossless Deamortization for Dynamic Greedy Set Cover
von: Solomon, Shay, et al.
Veröffentlicht: (2024)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Faster Dynamic $(Δ+1)$-Coloring Against Adaptive Adversaries
von: Flin, Maxime, et al.
Veröffentlicht: (2025)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

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

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time
von: Kowalik, Lukasz
Veröffentlicht: (2024)

Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors
von: Wang, Yulin, et al.
Veröffentlicht: (2023)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
von: Assadi, Sepehr
Veröffentlicht: (2024)

Tree-Like Shortcuttings of Trees
von: Le, Hung, et al.
Veröffentlicht: (2025)

Connectivity Labeling in Faulty Colored Graphs
von: Petruschka, Asaf, et al.
Veröffentlicht: (2024)

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

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2025)

Engineering Fully Dynamic Exact $Δ$-Orientation Algorithms
von: Großmann, Ernestine, et al.
Veröffentlicht: (2024)

Efficient Parallel $(Δ+1)$-Edge-Coloring
von: Elkin, Michael, et al.
Veröffentlicht: (2026)

Fully Dynamic Euclidean k-Means
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2025)

Chasing Positive Bodies
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
von: Parter, Merav, et al.
Veröffentlicht: (2024)

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

Approximate Light Spanners in Planar Graphs
von: Le, Hung, et al.
Veröffentlicht: (2025)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
von: Assadi, Sepehr, et al.
Veröffentlicht: (2022)

Deterministic Edge Coloring with few Colors in CONGEST
von: Blikstad, Joakim, et al.
Veröffentlicht: (2026)