2020 journal article
Efficient algorithms for finding2-mediansof a tree
NETWORKS, 77(3), 383–402.
author keywords: 2-median; binary search; linear time; priority queue; sorting; trees
TL;DR:
A framework that unifies all efficient algorithms for the 2‐median problem on trees is presented, which isolates the nonlinear part of the computation so that future time‐bound improvements are easily incorporated.
(via Semantic Scholar)
open access via www.lib.ncsu.edu (repository)
Source: Web Of Science
Added: October 5, 2020
AbstractThe p‐median problem for networks is NP‐hard, but polynomial time algorithms exist for trees (n is the number of nodes): O(pn2) by Tamir, and O(n lgp + 2 n) by Benkoczi and Bhattacharya. Goldman gave an O(n) algorithm for the 1‐median problem on trees. Mirchandani and Oudjit proved localization properties for 2‐medians on trees; these were later used to obtain an O(nlg n) bound, and, in special cases, O(n) . We present a framework that unifies all efficient algorithms for the 2‐median problem on trees. Our framework isolates the nonlinear part of the computation so that future time‐bound improvements are easily incorporated. We also introduce a method for reducing the search space, improving all known runtimes in many instances. Finally, we give a new algorithm for the case where edge lengths are positive integers. The associated time bound is O(n + D) , where D is the sum of the logarithms of edge lengths. This is O(n) if edge lengths are bounded by a constant and O(n lglg n) if they are O(lg n) . The algorithm is flexible enough to extend to noninteger edge lengths, preserving the time bound in some circumstances.