An $O(n\log ^2 n)$ Algorithm for the <i>k</i>th Longest Path in a Tree with Applications to Location Problems

Abstract

Many known algorithms are based on selection in a set whose cardinality is superlinear in terms of the input length. It is desirable in these cases to have selection algorithms that run in sublinear time in terms of the cardinality of the set. This paper presents a successful development in this direction. The methods developed here are applied to improve the previously known upper bounds for the time complexity of various location problems.