Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910551136796672 |
|---|---|
| author | Bhattacharya, Sayan Costa, Martín Panski, Nadav Solomon, Shay |
| author_facet | Bhattacharya, Sayan Costa, Martín Panski, Nadav Solomon, Shay |
| contents | Vizing's theorem asserts the existence of a $(Δ+1)$-edge coloring for any graph $G$, where $Δ= Δ(G)$ denotes the maximum degree of $G$. Several polynomial time $(Δ+1)$-edge coloring algorithms are known, and the state-of-the-art running time (up to polylogarithmic factors) is $\tilde{O}(\min\{m \cdot \sqrt{n}, m \cdot Δ\})$, by Gabow et al.\ from 1985, where $n$ and $m$ denote the number of vertices and edges in the graph, respectively. (The $\tilde{O}$ notation suppresses polylogarithmic factors.) Recently, Sinnamon shaved off a polylogarithmic factor from the time bound of Gabow et al.
The {arboricity} $α= α(G)$ of a graph $G$ is the minimum number of edge-disjoint forests into which its edge set can be partitioned, and it is a measure of the graph's "uniform density". While $α\le Δ$ in any graph, many natural and real-world graphs exhibit a significant separation between $α$ and $Δ$.
In this work we design a $(Δ+1)$-edge coloring algorithm with a running time of $\tilde{O}(\min\{m \cdot \sqrt{n}, m \cdot Δ\})\cdot \fracαΔ$, thus improving the longstanding time barrier by a factor of $\fracαΔ$. In particular, we achieve a near-linear runtime for bounded arboricity graphs (i.e., $α= \tilde{O}(1)$) as well as when $α= \tilde{O}(\fracΔ{\sqrt{n}})$. Our algorithm builds on Sinnamon's algorithm, and can be viewed as a density-sensitive refinement of it. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_02415 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring Bhattacharya, Sayan Costa, Martín Panski, Nadav Solomon, Shay Data Structures and Algorithms Vizing's theorem asserts the existence of a $(Δ+1)$-edge coloring for any graph $G$, where $Δ= Δ(G)$ denotes the maximum degree of $G$. Several polynomial time $(Δ+1)$-edge coloring algorithms are known, and the state-of-the-art running time (up to polylogarithmic factors) is $\tilde{O}(\min\{m \cdot \sqrt{n}, m \cdot Δ\})$, by Gabow et al.\ from 1985, where $n$ and $m$ denote the number of vertices and edges in the graph, respectively. (The $\tilde{O}$ notation suppresses polylogarithmic factors.) Recently, Sinnamon shaved off a polylogarithmic factor from the time bound of Gabow et al. The {arboricity} $α= α(G)$ of a graph $G$ is the minimum number of edge-disjoint forests into which its edge set can be partitioned, and it is a measure of the graph's "uniform density". While $α\le Δ$ in any graph, many natural and real-world graphs exhibit a significant separation between $α$ and $Δ$. In this work we design a $(Δ+1)$-edge coloring algorithm with a running time of $\tilde{O}(\min\{m \cdot \sqrt{n}, m \cdot Δ\})\cdot \fracαΔ$, thus improving the longstanding time barrier by a factor of $\fracαΔ$. In particular, we achieve a near-linear runtime for bounded arboricity graphs (i.e., $α= \tilde{O}(1)$) as well as when $α= \tilde{O}(\fracΔ{\sqrt{n}})$. Our algorithm builds on Sinnamon's algorithm, and can be viewed as a density-sensitive refinement of it. |
| title | Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2307.02415 |