Approximation algorithms for inner-node weighted minimum spanning trees

摘要

This paper addresses the Inner-node Weighted Minimum Spanning Tree Problem (IWMST), which asks lor a spanning tree in a graph G = (V, E) (|V|= n,|E|=m) with the minimum total cost for its edges and non-leal nodes. This problem is NP lard because it contains the connected dominating set problem (CDS) as a special case. Since CDS cannot be approximated with a factor of (1 - ε)H(Δ) (Δ is the maximum degree) unless NP￠DTIME|n~(O(log log n))| [10], we can only expect a poly-logarithmic approximation algorithm for the IWMST problem.rnTo tackle this problem, we first present a general framework for developing poly-logarithmic approximation algorithms. Our framework aims to find a k/k-1approximate Algorithm (k ∈ N and k≥2) for the IWMST problem. Based on this framework, we further design two polynomial time approximation algorithms. The first one can find a 2ln n-approximate solution in O(mn log n) time, while the second one can compute a 1.5ln n-approximate solution in O(n~2Δ~6) time (Δ is the maximum degree in G). We have also studied the relationships between the IWMST problem and several other similar problems.