Cover Image

Faster Vizing and Near-Vizing Edge Coloring Algorithms

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Assadi, Sepehr
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
by: Dhawan, Abhishek
Published: (2024)

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

Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
by: Sadeh, Yaniv, et al.
Published: (2026)

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

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

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

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

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

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

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

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

The planar edge-coloring theorem of Vizing in $O(n\log n)$ time
by: Jędrzejczak, Patryk, et al.
Published: (2025)

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

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

Fast algorithms for Vizing's theorem on bounded degree graphs
by: Bernshteyn, Anton, et al.
Published: (2023)

Faster Edge Coloring by Partition Sieving
by: Akmal, Shyan, et al.
Published: (2025)

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

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

Online Edge Coloring is (Nearly) as Easy as Offline
by: Blikstad, Joakim, et al.
Published: (2024)

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

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

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

Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut
by: Baswana, Surender, et al.
Published: (2025)

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

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

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

Faster Deterministic Streaming Vertex Coloring
by: Chechik, Shiri, et al.
Published: (2026)

Faster Algorithms for Graph Monopolarity
by: Philip, Geevarghese, et al.
Published: (2024)

Simple and Faster Algorithms for Knapsack
by: He, Qizheng, et al.
Published: (2023)

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

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

Faster Algorithms for Longest Common Substring
by: Charalampopoulos, Panagiotis, et al.
Published: (2021)

A Near-Real-Time Reduction-Based Algorithm for Coloring Massive Graphs
by: Zhu, Chenghao, et al.
Published: (2025)

Faster Algorithms for Dual-Failure Replacement Paths
by: Chechik, Shiri, et al.
Published: (2024)

A Faster Algorithm for Pigeonhole Equal Sums
by: Jin, Ce, et al.
Published: (2024)

Faster Algorithms for Shortest Unique or Absent Substrings
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

Faster Algorithms for Text-to-Pattern Hamming Distances
by: Chan, Timothy M., et al.
Published: (2023)

A Faster Algorithm for Constrained Correlation Clustering
by: Fischer, Nick, et al.
Published: (2025)