Quantum Algorithms and Lower Bounds for Eccentricity, Radius, and Diameter in Undirected Graphs
Adam Wesołowski, Jinge Bao · 2025
Read Quantum Algorithms and Lower Bounds for Eccentricity, Radius, and Diameter in Undirected Graphs by Adam Wesołowski, Jinge Bao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-20148.txt.
Description
Adam Wesolowski and Jinge Bao give quantum algorithms and lower bounds for three classic graph measures, in work from 2025. Eccentricity, radius, and diameter all rest on distances between points in a graph. They are basic tools for reading network shape, from roads to social links.
Their quantum algorithms find the diameter and radius of weighted, undirected graphs, along with the paths that achieve them. The run time beats classic limits in the model they use. A second algorithm estimates the diameter within a set factor, faster still. Lower bounds, proved by reduction from a minimum finding problem, show that no quantum method can do much better.
Catalog record
| CREATOR | Adam Wesołowski, Jinge Bao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-20148