Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913689512181760 |
|---|---|
| author | Dhawan, Abhishek |
| author_facet | Dhawan, Abhishek |
| contents | Let $ε\in (0, 1)$ and $n, Δ\in \mathbb N$ be such that $Δ= Ω\left(\max\left\{\frac{\log n}ε,\, \left(\frac{1}ε\log \frac{1}ε\right)^2\right\}\right)$. Given an $n$-vertex $m$-edge simple graph $G$ of maximum degree $Δ$, we present a randomized $O\left(m\,\log^3 Δ\,/\,ε^2\right)$-time algorithm that computes a proper $(1+ε)Δ$-edge-coloring of $G$ with high probability. This improves upon the best known results for a wide range of the parameters $ε$, $n$, and $Δ$. Our approach combines a flagging strategy from earlier work of the author with a shifting procedure employed by Duan, He, and Zhang for dynamic edge-coloring. The resulting algorithm is simple to implement and may be of practical interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16692 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs Dhawan, Abhishek Data Structures and Algorithms Combinatorics Let $ε\in (0, 1)$ and $n, Δ\in \mathbb N$ be such that $Δ= Ω\left(\max\left\{\frac{\log n}ε,\, \left(\frac{1}ε\log \frac{1}ε\right)^2\right\}\right)$. Given an $n$-vertex $m$-edge simple graph $G$ of maximum degree $Δ$, we present a randomized $O\left(m\,\log^3 Δ\,/\,ε^2\right)$-time algorithm that computes a proper $(1+ε)Δ$-edge-coloring of $G$ with high probability. This improves upon the best known results for a wide range of the parameters $ε$, $n$, and $Δ$. Our approach combines a flagging strategy from earlier work of the author with a shifting procedure employed by Duan, He, and Zhang for dynamic edge-coloring. The resulting algorithm is simple to implement and may be of practical interest. |
| title | Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2408.16692 |