An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems

Authors:
  • NMN. Megiddo
    N. Megiddo
  • ATA. Tamir
    A. Tamir
  • EZE. Zemel
    E. Zemel
  • RCR. Chandrasekaran
    R. Chandrasekaran

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.

This publication has 11 references indexed in Scilit: