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

CREATORAdam Wesołowski, Jinge Bao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-20148

Browse the full library · About the Tower of Babel