Loading...
Please wait, while we are loading the content...
Similar Documents
Title Finding Subsets Maximizing Minimum Structures
| Content Provider | Semantic Scholar |
|---|---|
| Author | Iwano, Kazuo |
| Copyright Year | 2018 |
| Abstract | 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/84653/1/026.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
