An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
Authors:
- N. MegiddoNMN. Megiddo
- A. TamirATA. Tamir
- E. ZemelEZE. Zemel
- R. ChandrasekaranRCR. Chandrasekaran
- 1 May 1981
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 10 (2) , 328-337
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.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Location on Tree Networks: P-Centre and n-Dispersion ProblemsMathematics of Operations Research, 1981
- An Algorithmic Approach to Network Location Problems. I: Thep-CentersSIAM Journal on Applied Mathematics, 1979
- A Fast Selection Algorithm and the Problem of Optimum Distribution of EffortJournal of the ACM, 1979
- Lower Bounds for Selection in X + Y and Other MultisetsJournal of the ACM, 1978
- Finding Two-Centers of a Tree: The Continuous CaseTransportation Science, 1978
- Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $SIAM Journal on Computing, 1978
- Time bounds for selectionJournal of Computer and System Sciences, 1973
- Optimal Center Location in Simple NetworksTransportation Science, 1971
- Discrete Optimization Via Marginal AnalysisManagement Science, 1966
- Sur les assemblages de lignes.Journal für die reine und angewandte Mathematik (Crelles Journal), 1869