Imagen de Portada

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Assadi, Sepehr, Yazdanyar, Helia
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

Faster Vizing and Near-Vizing Edge Coloring Algorithms
por: Assadi, Sepehr
Publicado: (2024)

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

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

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

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

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

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

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

DTC: Real-Time and Accurate Distributed Triangle Counting in Fully Dynamic Graph Streams
por: Xuan, Wei, et al.
Publicado: (2025)

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

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

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

Triangle-Covered Graphs: Algorithms, Complexity, and Structure
por: Madani, Amirali, et al.
Publicado: (2025)

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

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

Triangle Detection in H-Free Graphs
por: Abboud, Amir, et al.
Publicado: (2025)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
por: Chuzhoy, Julia, et al.
Publicado: (2026)

Fully Dynamic Algorithms for Chamfer Distance
por: Goranci, Gramoz, et al.
Publicado: (2025)

Fully Dynamic Algorithms for Transitive Reduction
por: Goranci, Gramoz, et al.
Publicado: (2025)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
por: Abboud, Amir, et al.
Publicado: (2026)

Simple Algorithms for Fully Dynamic Edge Connectivity
por: Kenneth-Mordoch, Yotam, et al.
Publicado: (2025)

An Improved Approximation Algorithm for Metric Triangle Packing
por: Zhao, Jingyang, et al.
Publicado: (2024)

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

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
por: El-Hayek, Antoine, et al.
Publicado: (2023)

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

Fully Dynamic Graph Algorithms with Edge Differential Privacy
por: Raskhodnikova, Sofya, et al.
Publicado: (2024)

Graph Coloring Below Guarantees via Co-Triangle Packing
por: Akmal, Shyan, et al.
Publicado: (2025)

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

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
por: Bansal, Nikhil, et al.
Publicado: (2026)

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
por: Behnezhad, Soheil, et al.
Publicado: (2024)

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
por: Zhao, Yibin
Publicado: (2025)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
por: Chuzhoy, Julia, et al.
Publicado: (2026)

Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering
por: Adriaens, Florian, et al.
Publicado: (2026)

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

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
por: Khanna, Sanjeev, et al.
Publicado: (2025)

Near Uniform Triangle Sampling Over Adjacency List Graph Streams
por: Bishnu, Arijit, et al.
Publicado: (2024)

Dynamic Graph Coloring: Sequential, Parallel, and Distributed
por: Ghaffari, Mohsen, et al.
Publicado: (2025)