Magnús M. Halldórsson, Guy Kortsarz, et al.
ACM Transactions on Algorithms
We consider the problem of finding a set of k vertices in a graph that are in some sense remote. Stated more formally, given a graph G and an integer k, find a set P of k vertices for which the total weight of a minimum structure on P is maximized. In particular, we are interested in three problems of this type, where the structure to be minimized is a spanning tree (REMOTE-MST), Steiner tree, or traveling salesperson tour. We study a natural greedy algorithm that simultaneously approximates all three problems on metric graphs. For instance, its performance ratio for REMOTE-MST is exactly 4, while this problem is N P-hard to approximate within a factor of less than 2. We also give a better approximation for graphs induced by Euclidean points in the plane, present an exact algorithm for graphs whose distances correspond to shortest-path distances in a tree, and prove hardness and approximability results for general graphs.
Magnús M. Halldórsson, Guy Kortsarz, et al.
ACM Transactions on Algorithms
Naoki Katoh, Takeshi Tokuyama, et al.
FOCS 1992
Alok Aggarwal, Hiros HiImait, et al.
SCG 1989
Tetsuo Asano, Danny Z. Chen, et al.
SODA 1996