Buchumschlag

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Behnezhad, Soheil, Rajaraman, Rajmohan, Wasim, Omer
Format:	Preprint
Veröffentlicht:	2024
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

Competitive Capacitated Online Recoloring
von: Rajaraman, Rajmohan, et al.
Veröffentlicht: (2024)

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

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

Approximating Maximum Matching Requires Almost Quadratic Time
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Single-Pass Streaming CSPs via Two-Tier Sampling
von: Azarmehr, Amir, et al.
Veröffentlicht: (2026)

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

Stochastic Matching via In-n-Out Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Half-Approximating Maximum Dicut in the Streaming Setting
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Lower Bounds for Non-adaptive Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Sublinear Algorithms for TSP via Path Covers
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2023)

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

Markov Chains with Rewinding
von: Azarmehr, Amir, et al.
Veröffentlicht: (2026)

Correlation Clustering Beyond the Pivot Algorithm
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

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

Massively Parallel Minimum Spanning Tree in General Metric Spaces
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

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

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

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

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

Chasing Small Sets Optimally Against Adaptive Adversaries
von: Coester, Christian, et al.
Veröffentlicht: (2026)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2026)

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

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

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

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

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

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

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

Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
von: Banihashem, Kiarash, et al.
Veröffentlicht: (2025)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
von: Grilnberger, Mara, et al.
Veröffentlicht: (2026)

Robust Streaming Against Low-Memory Adversaries
von: Ben-Eliezer, Omri, et al.
Veröffentlicht: (2025)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

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

Fully Dynamic Algorithms for Chamfer Distance
von: Goranci, Gramoz, et al.
Veröffentlicht: (2025)

Fully Dynamic Algorithms for Transitive Reduction
von: Goranci, Gramoz, et al.
Veröffentlicht: (2025)

Fully Dynamic Spectral Sparsification of Hypergraphs
von: Goranci, Gramoz, et al.
Veröffentlicht: (2025)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
von: Braverman, Vladimir, et al.
Veröffentlicht: (2024)