Premium
Approximating minimum spanning tree of depth 2
Author(s) -
Alfandari L.,
Paschos V.T.
Publication year - 1999
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.1999.tb00176.x
Subject(s) - spanning tree , combinatorics , connected dominating set , mathematics , minimum spanning tree , k minimum spanning tree , approximation algorithm , polynomial time approximation scheme , steiner tree problem , time complexity , discrete mathematics , graph , metric (unit) , k ary tree , binary tree , tree structure , operations management , economics
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 .