Finding Centers and Medians of a Tree by Distance Queries

摘要

We investigate the problem of finding centers and medians of a tree on the distance oracle model. In this model, the tree is not given as the input and the cost is counted by the number of performed queries for distances between leaves. We show that 2n - 3 queries are necessary and sufficient for finding the diameter, the radius, and the centers, where n is the number of leaves. For the median problem, we propose an n lg n-queries deterministic algorithm and a randomized algorithm with less than 6n expected queries.