Approximating minimum spanning tree of depth 2
Alfandari, Laurent; Paschos, Vangelis (1999), Approximating minimum spanning tree of depth 2, International Transactions in Operational Research, 6, 6, p. 607-622. http://dx.doi.org/10.1111/j.1475-3995.1999.tb00176.x
TypeArticle accepté pour publication ou publié
Journal nameInternational Transactions in Operational Research
MetadataShow full item record
Abstract (EN)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)lnn), 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 lnn.
Subjects / KeywordsSet covering; Spanning tree; Polynomial approximation; Complexity; Graph
Showing items related by title and author.