Copertina

A linear-time algorithm for $(1+ε)Δ$-edge-coloring

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bernshteyn, Anton, Dhawan, Abhishek
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Discrete Mathematics Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
di: Bencs, Ferenc, et al.
Pubblicazione: (2024)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
di: Korhonen, Tuukka, et al.
Pubblicazione: (2024)

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

A new width parameter of graphs based on edge cuts: $α$-edge-crossing width
di: Chang, Yeonsu, et al.
Pubblicazione: (2023)

Strong spatial mixing for colorings on trees and its algorithmic applications
di: Chen, Zongchen, et al.
Pubblicazione: (2023)

Perturbation results for distance-edge-monitoring numbers
di: Yang, Chenxu, et al.
Pubblicazione: (2023)

Approximating maximum-size properly colored forests
di: Bai, Yuhang, et al.
Pubblicazione: (2024)

Improved bounds for coloring locally sparse hypergraphs
di: Iliopoulos, Fotis
Pubblicazione: (2020)

Sharp Online Hardness for Large Balanced Independent Sets
di: Dhawan, Abhishek, et al.
Pubblicazione: (2025)

A logarithmic approximation of linearly ordered colourings
di: Håstad, Johan, et al.
Pubblicazione: (2024)

Towards Transitive-free Digraphs
di: Abhinav, Ankit, et al.
Pubblicazione: (2025)

Parameterised algorithms for temporally satisfying reconfiguration problems
di: Davot, Tom, et al.
Pubblicazione: (2025)

Efficient algorithms for the Potts model on small-set expanders
di: Carlson, Charles, et al.
Pubblicazione: (2020)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
di: Galby, Esther, et al.
Pubblicazione: (2025)

Generalising the maximum independent set algorithm via Boolean networks
di: Gadouleau, Maximilien, et al.
Pubblicazione: (2024)

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
di: Alecu, Bogdan, et al.
Pubblicazione: (2024)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
di: Deák, Bence, et al.
Pubblicazione: (2026)

Quasi-linear distance query reconstruction for graphs of bounded treelength
di: Bastide, Paul, et al.
Pubblicazione: (2024)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
di: Arkhipov, Pavel, et al.
Pubblicazione: (2024)

An efficient algorithm for $\mathcal{F}$-subgraph-free Edge Deletion on graphs having a product structure
di: An, Shinwoo, et al.
Pubblicazione: (2025)

Totally $Δ$-modular IPs with two non-zeros in most rows
di: Kober, Stefan
Pubblicazione: (2024)

On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
di: Ghanbari, Babak, et al.
Pubblicazione: (2025)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
di: Dhawan, Abhishek, et al.
Pubblicazione: (2026)

Traversing combinatorial 0/1-polytopes via optimization
di: Merino, Arturo, et al.
Pubblicazione: (2023)

A characterization of testable hypergraph properties
di: Joos, Felix, et al.
Pubblicazione: (2017)

A Uniformly Random Solution to Algorithmic Redistricting
di: Cai, Jin-Yi, et al.
Pubblicazione: (2024)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
di: Iwata, Satoru, et al.
Pubblicazione: (2024)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
di: Bourneuf, Romain, et al.
Pubblicazione: (2025)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
di: Bourneuf, Romain, et al.
Pubblicazione: (2025)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
di: Jana, Satyabrata, et al.
Pubblicazione: (2025)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
di: Shakeri, Heman, et al.
Pubblicazione: (2025)

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

Algorithms and complexity for monitoring edge-geodetic sets in graphs
di: Foucaud, Florent, et al.
Pubblicazione: (2024)

An algorithm with a delay of $\mathcal{O}(kΔ)$ for enumerating connected induced subgraphs of size $k$
di: Xiao, Chenglong, et al.
Pubblicazione: (2024)

Problems on Group-labeled Matroid Bases
di: Hörsch, Florian, et al.
Pubblicazione: (2024)

$α_i$-Metric Graphs: Hyperbolicity
di: Dragan, Feodor F., et al.
Pubblicazione: (2024)

Rainbow Arborescence Conjecture
di: Bérczi, Kristóf, et al.
Pubblicazione: (2024)

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
di: Holtgrefe, Niels, et al.
Pubblicazione: (2024)