A linear-time algorithm for $(1+ε)Δ$-edge-coloring
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929701624217600 |
|---|---|
| author | Bernshteyn, Anton Dhawan, Abhishek |
| author_facet | Bernshteyn, Anton Dhawan, Abhishek |
| contents | We present a randomized algorithm that, given a constant $ε> 0$, outputs a proper $(1+ε)Δ$-edge-coloring of an $m$-edge simple graph $G$ of maximum degree $Δ\geq 1/ε$ in $O(m)$ time with high probability. This is the first linear-time algorithm for this problem covering the full range of possible values of $Δ$. Indeed, even for edge-coloring with $2Δ- 1$ colors (i.e., meeting the "greedy" bound), no such linear-time algorithm has been previously known. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_04887 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A linear-time algorithm for $(1+ε)Δ$-edge-coloring Bernshteyn, Anton Dhawan, Abhishek Data Structures and Algorithms Discrete Mathematics Combinatorics We present a randomized algorithm that, given a constant $ε> 0$, outputs a proper $(1+ε)Δ$-edge-coloring of an $m$-edge simple graph $G$ of maximum degree $Δ\geq 1/ε$ in $O(m)$ time with high probability. This is the first linear-time algorithm for this problem covering the full range of possible values of $Δ$. Indeed, even for edge-coloring with $2Δ- 1$ colors (i.e., meeting the "greedy" bound), no such linear-time algorithm has been previously known. |
| title | A linear-time algorithm for $(1+ε)Δ$-edge-coloring |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2407.04887 |