Approximating minimum spanning tree of depth 2

Approximating minimum spanning tree of depth 2

0.00 Avg rating0 Votes
Article ID: iaor20012482
Country: United Kingdom
Volume: 6
Issue: 6
Start Page Number: 607
End Page Number: 622
Publication Date: Nov 1999
Journal: International Transactions in Operational Research
Authors: ,
Keywords: minimum spanning tree
Abstract:

We prove that the problem of finding, in an undirected graph with non-negative costs on edges, a minimum cost rooted spanning tree of depth 2 is NP-hard. We then prove that, in a graph of order n, this problem cannot be approximated within better than O(ln n), unless problems in NP can be solved by slightly superpolynomial algorithms. We also prove that the metric version of the problem is MAX-SNP-hard and, consequently, cannot be approximated by polynomial time approximation schemes, unless P = NP. We devise approximation algorithms for several restricted cases and, finally, a polynomial time algorithm approximating the general problem within ratio ln n.

Reviews

Required fields are marked *. Your email address will not be published.