Finding the diameter of a tree with distance queries

September 27, 2025 Β· Declared Dead Β· πŸ› arXiv.org

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors DΓ‘niel Gerbner, AndrΓ‘s Imolay, Kartal Nagy, BalΓ‘zs PatkΓ³s, KristΓ³f ZΓ³lomy arXiv ID 2509.23326 Category cs.DS: Data Structures & Algorithms Cross-listed math.CO Citations 0 Venue arXiv.org Last Checked 4 months ago
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.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted