Buchumschlag

Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Sadeh, Yaniv, Kaplan, Haim
Format:	Preprint
Veröffentlicht:	2026
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

Dynamic Edge Coloring of Forests
von: Kaplan, Haim, et al.
Veröffentlicht: (2026)

Caching Connections in Matchings
von: Sadeh, Yaniv, et al.
Veröffentlicht: (2023)

Search Trees on Trees via LP
von: Sadeh, Yaniv, et al.
Veröffentlicht: (2025)

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

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

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
von: Dhawan, Abhishek
Veröffentlicht: (2024)

Improved Tree Sparsifiers in Near-Linear Time
von: Agassy, Daniel, et al.
Veröffentlicht: (2025)

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

A Simple Algorithm for Dynamic Carpooling with Recourse
von: Efron, Yuval, et al.
Veröffentlicht: (2024)

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

Fully-Dynamic Submodular Cover with Bounded Recourse
von: Gupta, Anupam, et al.
Veröffentlicht: (2020)

Improved Streaming Edge Coloring
von: Chechik, Shiri, et al.
Veröffentlicht: (2025)

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

Expander Decomposition for Non-Uniform Vertex Measures
von: Agassy, Daniel, et al.
Veröffentlicht: (2025)

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
von: Agassy, Daniel, et al.
Veröffentlicht: (2022)

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

Online Steiner Forest with Recourse
von: Long, Yaowei, et al.
Veröffentlicht: (2026)

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

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

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

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
von: El-Hayek, Antoine, et al.
Veröffentlicht: (2023)

Dynamic Consistent $k$-Center Clustering with Optimal Recourse
von: Forster, Sebastian, et al.
Veröffentlicht: (2024)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
von: Meierhans, Simon, et al.
Veröffentlicht: (2025)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
von: Gupta, Anupam, et al.
Veröffentlicht: (2026)

On Differentially Private Linear Algebra
von: Kaplan, Haim, et al.
Veröffentlicht: (2024)

A Little Clairvoyance Is All You Need
von: Gupta, Anupam, et al.
Veröffentlicht: (2025)

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

Faster All-Pairs Optimal Electric Car Routing
von: Dorfman, Dani, et al.
Veröffentlicht: (2025)

Online Edge Coloring: Sharp Thresholds
von: Blikstad, Joakim, et al.
Veröffentlicht: (2025)

Faster Edge Coloring by Partition Sieving
von: Akmal, Shyan, et al.
Veröffentlicht: (2025)

Deterministic Online Bipartite Edge Coloring
von: Blikstad, Joakim, et al.
Veröffentlicht: (2024)

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

Overlapping and Robust Edge-Colored Clustering in Hypergraphs
von: Crane, Alex, et al.
Veröffentlicht: (2023)

Streaming Edge Coloring with Subquadratic Palette Size
von: Chechik, Shiri, et al.
Veröffentlicht: (2023)

On the Complexity of Distributed Edge Coloring and Orientation Problems
von: Brandt, Sebastian, et al.
Veröffentlicht: (2025)

Online Edge Coloring is (Nearly) as Easy as Offline
von: Blikstad, Joakim, et al.
Veröffentlicht: (2024)

Dynamic Connectivity in Disk Graphs
von: Baumann, Alexander, et al.
Veröffentlicht: (2021)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Learning-Augmented Algorithms with Explicit Predictors
von: Elias, Marek, et al.
Veröffentlicht: (2024)

The Cost of Consistency: Submodular Maximization with Constant Recourse
von: Dütting, Paul, et al.
Veröffentlicht: (2024)