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
Type
Article accepté pour publication ou publiéDate
1999Journal name
International Transactions in Operational ResearchVolume
6Number
6Publisher
Wiley
Pages
607-622
Publication identifier
Metadata
Show full item recordAbstract (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 / Keywords
Set covering; Spanning tree; Polynomial approximation; Complexity; GraphRelated items
Showing items related by title and author.
-
Alfandari, Laurent; Paschos, Vangelis (1997) Communication / Conférence
-
Paschos, Stratos; Paschos, Vangelis (2012) Article accepté pour publication ou publié
-
Alfandari, Laurent; Paschos, Vangelis (1998) Communication / Conférence
-
Boria, Nicolas; Paschos, Vangelis (2010) Article accepté pour publication ou publié
-
Alfandari, Laurent (2001) Article accepté pour publication ou publié