October 20, 2025Open Access

Finding the diameter of a tree with distance queries

Key Points

Optimal adaptive algorithms can find two vertices of maximal distance with a limited number of distance queries.
Exact numbers of queries are derived for non-adaptive versions of the problems involving hidden trees.
The study focuses on trees with specific properties, using distance queries to ascertain key metrics.
Results indicate an asymptotic number of queries necessary to identify the hidden tree structure.

Abstract

We study the number of distance queries needed to identify certain properties of a hidden tree T on n vertices. A distance query consists of two vertices x, y, and the answer is the distance of x and y in T. We determine the number of queries an optimal adaptive algorithm needs to find two vertices of maximal distance up to an additive constant, and the number of queries needed to identify the hidden tree asymptotically. We also study the non-adaptive versions of these problems, determining the number of queries needed exactly.

Read Full Paperexternally

Bookmark

View Full Paper

Cite This Study

Gerbner et al. (Sat,) studied this question.

synapsesocial.com/papers/68f6379bb481a140a36cf412 https://doi.org/https://doi.org/10.48550/arxiv.2509.23326

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Bookmark

View Full Paper