Copertina

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Assadi, Sepehr, Yazdanyar, Helia
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
di: Assadi, Sepehr, et al.
Pubblicazione: (2026)

Coloring Graphs with Few Colors in the Streaming Model
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
di: Assadi, Sepehr
Pubblicazione: (2024)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

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

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
di: Assadi, Sepehr
Pubblicazione: (2023)

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

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

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

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

Simple and Optimal Sublinear Algorithms for Mean Estimation
di: Bertolotti, Beatrice, et al.
Pubblicazione: (2024)

Palette Sparsification for Graphs with Sparse Neighborhoods
di: Dhawan, Abhishek
Pubblicazione: (2024)

Covering Approximate Shortest Paths with DAGs
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
di: Assadi, Sepehr, et al.
Pubblicazione: (2023)

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

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
di: Ferber, Asaf, et al.
Pubblicazione: (2025)

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

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

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

Streaming and Communication Complexity of Load-Balancing via Matching Contractors
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

Sublinear Algorithms for TSP via Path Covers
di: Behnezhad, Soheil, et al.
Pubblicazione: (2023)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
di: Kwok, Tsz Chiu, et al.
Pubblicazione: (2025)

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

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

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

Efficient Algorithms and New Characterizations for CSP Sparsification
di: Khanna, Sanjeev, et al.
Pubblicazione: (2024)

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

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

Distributed Triangle Detection is Hard in Few Rounds
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
di: Peng, Pan, et al.
Pubblicazione: (2025)

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

Faster Deterministic Streaming Vertex Coloring
di: Chechik, Shiri, et al.
Pubblicazione: (2026)

Bootstrapping Dynamic APSP via Sparsification
di: Kyng, Rasmus, et al.
Pubblicazione: (2024)

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

Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
di: Akhtar, Sheikh Shakil, et al.
Pubblicazione: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
di: Brand, Jan van den, et al.
Pubblicazione: (2026)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

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

Engineering Fully Dynamic Exact $Δ$-Orientation Algorithms
di: Großmann, Ernestine, et al.
Pubblicazione: (2024)