Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913710763671552 |
|---|---|
| author | Wesołowski, Adam Bao, Jinge |
| author_facet | Wesołowski, Adam Bao, Jinge |
| contents | The problems of computing eccentricity, radius, and diameter are fundamental to graph theory. These parameters are intrinsically defined based on the distance metric of the graph. In this work, we propose quantum algorithms for the diameter and radius of undirected, weighted graphs in the adjacency list model. The algorithms output diameter and radius with the corresponding paths in $\widetilde{O}(n\sqrt{m})$ time. Additionally, for the diameter, we present a quantum algorithm that approximates the diameter within a $2/3$ ratio in $\widetilde{O}(\sqrt{m}n^{3/4})$ time. We also establish quantum query lower bounds of $Ω(\sqrt{nm})$ for all the aforementioned problems through a reduction from the minima finding problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_20148 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs Wesołowski, Adam Bao, Jinge Quantum Physics Data Structures and Algorithms The problems of computing eccentricity, radius, and diameter are fundamental to graph theory. These parameters are intrinsically defined based on the distance metric of the graph. In this work, we propose quantum algorithms for the diameter and radius of undirected, weighted graphs in the adjacency list model. The algorithms output diameter and radius with the corresponding paths in $\widetilde{O}(n\sqrt{m})$ time. Additionally, for the diameter, we present a quantum algorithm that approximates the diameter within a $2/3$ ratio in $\widetilde{O}(\sqrt{m}n^{3/4})$ time. We also establish quantum query lower bounds of $Ω(\sqrt{nm})$ for all the aforementioned problems through a reduction from the minima finding problem. |
| title | Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.20148 |