Academic
Publications
Improved Approximation Algorithms for the Spanning Star Forest Problem

Improved Approximation Algorithms for the Spanning Star Forest Problem,10.1007/978-3-540-74208-1_4,Ning Chen,Roee Engelberg,C. Thach Nguyen,Prasad Rag

Improved Approximation Algorithms for the Spanning Star Forest Problem   (Citations: 5)
BibTex | RIS | RefWorks Download
A star graph is a tree of diameter at most two. A star forest is a graph that consists of node-disjoint star graphs. In the spanning star forest problem, given an unweighted graph G, the objective is to find a star forest that contains all the vertices of G and has the maximum number of edges. This problem is the complement of the dominating set problem in the following sense: On a graph with n vertices, the size of the maximum spanning star forest is equal to n minus the size of the minimum dominating set. We present a 0.71-approximation algorithm for this problem, improving upon the approximation factor of 0.6 of Nguyen et al. (9). We also present a 0.64-approximation algorithm for the problem on node-weighted graphs. Finally, we present improved hardness of approximation results for the weighted versions of the problem.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: