Answers are grounded in this paper and cite their sources.
Demonstrates efficient approximation of remote structures in graphs, implying improved computational feasibility.
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 NP-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.
No takes yet. Share an insight, caveat, or question.
Halldórsson et al. (1999) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: