Lecture Notes in Computer Science, 2007, Volume 4619/2007, 529-540, DOI: 10.1007/978-3-540-73951-7_46

Optimal Algorithms for the Weighted p -Center Problems on the Real Line for Small p

Binay Bhattacharya and Qiaosheng Shi

View Related Documents

Abstract

An optimal linear time algorithm for the unweighted p-center problems in trees has been known since 1991 [4]. No such worst-case linear time result is known for the weighted version of the p-center problems, even for a path graph. In this paper, for fixed p, we propose two linear-time algorithms for the weighted p-center problem for points on the real line, thereby partially resolving a long-standing open problem. One of our approaches generalizes the trimming technique of Megiddo [10], and the other one is based on the parametric pruning technique, introduced here. The proposed solutions make use of the solutions of another variant of the center problem called the conditional center location problem [13].

Fulltext Preview

Image of the first page of the fulltext document