Copertina

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Assadi, Sepehr, Kumar, Pankaj, Mittal, Parth
Natura:	Preprint
Pubblicazione:	2022
Soggetti:	Data Structures and Algorithms F.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

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

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

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

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

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

Streaming Algorithms for Bin Packing and Vector Scheduling
di: Cormode, Graham, et al.
Pubblicazione: (2019)

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

Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams
di: Chakrabarti, Amit, et al.
Pubblicazione: (2024)

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)

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

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

Clustering Permutations: New Techniques with Streaming Applications
di: Chakraborty, Diptarka, et al.
Pubblicazione: (2022)

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

Colorful Vertex Recoloring of Bipartite Graphs
di: Patt-Shamir, Boaz, et al.
Pubblicazione: (2025)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
di: DeHaan, Ian, et al.
Pubblicazione: (2024)

A Faster Directed Single-Source Shortest Path Algorithm
di: Duan, Ran, et al.
Pubblicazione: (2026)

Semi-Streaming Algorithms for Hypergraph Matching
di: Reinstädtler, Henrik, et al.
Pubblicazione: (2025)

On the Parameterized Complexity of Diverse SAT
di: Misra, Neeldhara, et al.
Pubblicazione: (2024)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2025)

Semi-Streaming Algorithms for Graph Property Certification
di: Das, Avinandan, et al.
Pubblicazione: (2025)

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

Single-Pass Streaming CSPs via Two-Tier Sampling
di: Azarmehr, Amir, et al.
Pubblicazione: (2026)

Space Complexity of Minimum Cut Problems in Single-Pass Streams
di: Ding, Matthew, et al.
Pubblicazione: (2024)

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
di: Chuzhoy, Julia, et al.
Pubblicazione: (2025)

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

Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs
di: Mosenzon, Ron
Pubblicazione: (2025)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
di: Ferdous, S M, et al.
Pubblicazione: (2023)

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

Calculation of the Comparative Efficiency of Algorithms Using a Single Metric
di: Chakraborty, Arya
Pubblicazione: (2024)

The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs
di: Chauhan, Archit, et al.
Pubblicazione: (2024)

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
di: Buchbinder, Niv, et al.
Pubblicazione: (2026)

Algorithms for Distance Problems in Continuous Graphs
di: Cabello, Sergio, et al.
Pubblicazione: (2025)

A Linear-Time 1.5-Approximation for Broadcasting in k-Cycle Graphs
di: Bringolf, Jeffrey, et al.
Pubblicazione: (2025)

An Algorithmic Bridge Between Hamming and Levenshtein Distances
di: Goldenberg, Elazar, et al.
Pubblicazione: (2022)

Streaming Graph Algorithms in the Massively Parallel Computation Model
di: Czumaj, Artur, et al.
Pubblicazione: (2025)