Buchumschlag

Faster Dynamic $(Δ+1)$-Coloring Against Adaptive Adversaries

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Flin, Maxime, Halldórsson, Magnús M.
Format:	Preprint
Veröffentlicht:	2025
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

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

Decentralized Distributed Graph Coloring II: degree+1-Coloring Virtual Graphs
von: Flin, Maxime, et al.
Veröffentlicht: (2024)

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

Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
von: Flin, Maxime, et al.
Veröffentlicht: (2026)

Decentralized Distributed Graph Coloring: Cluster Graphs
von: Flin, Maxime, et al.
Veröffentlicht: (2024)

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

When MIS and Maximal Matching are Easy in the Congested Clique
von: Censor-Hillel, Keren, et al.
Veröffentlicht: (2025)

Distributed Delta-Coloring under Bandwidth Limitations
von: Maus, Yannic, et al.
Veröffentlicht: (2024)

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

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

Streaming Diameter of High-Dimensional Points
von: Halldórsson, Magnús M., et al.
Veröffentlicht: (2025)

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

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

Faster Distributed $Δ$-Coloring via Ruling Subgraphs
von: Bourreau, Yann, et al.
Veröffentlicht: (2025)

Faster Distributed $Δ$-Coloring via a Reduction to MIS
von: Bourreau, Yann, et al.
Veröffentlicht: (2025)

Unit Interval Selection in Random Order Streams
von: Alexandru, Cezar-Mihail, et al.
Veröffentlicht: (2026)

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

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

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

Faster Deterministic Streaming Vertex Coloring
von: Chechik, Shiri, et al.
Veröffentlicht: (2026)

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

Distributed Lovász Local Lemma under Bandwidth Limitations
von: Halldórsson, Magnús M., 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)

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

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

Adaptive Hashing: Faster Hash Functions with Fewer Collisions
von: Melis, Gábor
Veröffentlicht: (2026)

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

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)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2026)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
von: de Vos, Tijn, et al.
Veröffentlicht: (2024)

$Δ$-Motif: Parallel Subgraph Isomorphism via Tabular Operations
von: Wang, Yulun, et al.
Veröffentlicht: (2025)

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

Faster Algorithms for Text-to-Pattern Hamming Distances
von: Chan, Timothy M., et al.
Veröffentlicht: (2023)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
von: Kadria, Avi, et al.
Veröffentlicht: (2025)

Simple and Faster Algorithms for Knapsack
von: He, Qizheng, et al.
Veröffentlicht: (2023)

Faster optimal univariate microgaggregation
von: Stamm, Felix I., et al.
Veröffentlicht: (2024)

Faster Algorithms for Graph Monopolarity
von: Philip, Geevarghese, et al.
Veröffentlicht: (2024)

Faster Parameterized Vertex Multicut
von: Chu, Huairui, et al.
Veröffentlicht: (2026)