How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover

详细信息    查看全文

• 作者：Toshihiro Fujito
• 刊名：Lecture Notes in Computer Science
• 出版年：2006
• 出版时间：2006
• 年：2006
• 卷：4051
• 期：1
• 页码：pp.431-442
• 全文大小：223 KB

文摘

The minimum cost tree cover problem is to compute a minimum cost tree T in a given connected graph G with costs on the edges, such that the vertices of T form a vertex cover for G. The problem is supposed to arise in applications of vertex cover and edge dominating set when connectivity is additionally required in solutions. Whereas a linear-time 2-approximation algorithm for the unweighted case has been known for quite a while, the best approximation ratio known for the weighted case is 3. Moreover, the known 3-approximation algorithm for such case is far from practical in its efficiency. In this paper we present a fast, purely combinatorial 2-approximation algorithm for the minimum cost tree cover problem. It constructs a good approximate solution by trimming some leaves within a minimum spanning tree (MST), and to determine which leaves to trim, it uses both of the primal-dual schema and the local ratio technique in an interlaced fashion.