Buchumschlag

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Dhawan, Abhishek
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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)

Vizing's Theorem in Near-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Fast algorithms for Vizing's theorem on bounded degree graphs
von: Bernshteyn, Anton, et al.
Veröffentlicht: (2023)

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

Palette Sparsification for Graphs with Sparse Neighborhoods
von: Dhawan, Abhishek
Veröffentlicht: (2024)

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
von: Bernshteyn, Anton, et al.
Veröffentlicht: (2024)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
von: Korhonen, Tuukka
Veröffentlicht: (2024)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
von: Ghanbari, Babak, et al.
Veröffentlicht: (2026)

A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching
von: Izumi, Taisuke, et al.
Veröffentlicht: (2023)

Lightweight Near-Additive Spanners
von: Gitlitz, Yuval, et al.
Veröffentlicht: (2024)

A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices
von: Kano, Takumi, et al.
Veröffentlicht: (2026)

Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
von: Sadeh, Yaniv, et al.
Veröffentlicht: (2026)

The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring
von: Inoue, Yuta, et al.
Veröffentlicht: (2026)

Vizing's Theorem in Deterministic Almost-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Above-Guarantee Algorithm for Properly Colored Spanning Trees
von: Bai, Yuhang, et al.
Veröffentlicht: (2026)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2024)

Online Edge Coloring is (Nearly) as Easy as Offline
von: Blikstad, Joakim, et al.
Veröffentlicht: (2024)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
von: Bourneuf, Romain, et al.
Veröffentlicht: (2025)

An Alternate Proof of Near-Optimal Light Spanners
von: Bodwin, Greg
Veröffentlicht: (2023)

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

A Near-Real-Time Reduction-Based Algorithm for Coloring Massive Graphs
von: Zhu, Chenghao, et al.
Veröffentlicht: (2025)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
von: Fischer, Nick, et al.
Veröffentlicht: (2024)

Sampling Colorings with Fixed Color Class Sizes
von: Kuchukova, Aiya, et al.
Veröffentlicht: (2026)

A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
von: Kuszmaul, William
Veröffentlicht: (2025)

Improved Explicit Near-Optimal Codes in the High-Noise Regimes
von: Li, Xin, et al.
Veröffentlicht: (2024)

Approximating Partition in Near-Linear Time
von: Chen, Lin, et al.
Veröffentlicht: (2024)

Ghost Value Augmentation for $k$-Edge-Connectivity
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2023)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2026)

A Maximum Linear Arrangement Problem on Directed Graphs
von: DeVos, Matt, et al.
Veröffentlicht: (2018)

A Note on Generic Tangle Algorithms
von: Elbracht, Christian, et al.
Veröffentlicht: (2020)

Sharp Online Hardness for Large Balanced Independent Sets
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2025)

Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
von: Biedl, Therese, et al.
Veröffentlicht: (2024)

Improved Tree Sparsifiers in Near-Linear Time
von: Agassy, Daniel, et al.
Veröffentlicht: (2025)

A Lower Bound for the Max Entropy Algorithm for TSP
von: Jin, Billy, et al.
Veröffentlicht: (2023)

A Faster Deterministic Approximation Algorithm for TTP-2
von: Kanaya, Yuga, et al.
Veröffentlicht: (2023)

Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs
von: Choromanski, Krzysztof, et al.
Veröffentlicht: (2026)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
von: Dudeja, Aditi, et al.
Veröffentlicht: (2024)

Notes on the Linear Algebraic View of Regularity Lemmas
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications
von: Dumitrescu, Adrian
Veröffentlicht: (2024)