Academic
Publications
An Improved Approximation Algorithm for Spanning Star Forest in Dense Graphs

An Improved Approximation Algorithm for Spanning Star Forest in Dense Graphs,10.1007/978-3-642-17461-2_13,Jing He,Hongyu Liang

An Improved Approximation Algorithm for Spanning Star Forest in Dense Graphs  
BibTex | RIS | RefWorks Download
A spanning subgraph of a given graph G is called a spanning star forest of G if it is a collection of node-disjoint trees of depth at most 1 (such trees are called stars). The size of a spanning star forest is the number of leaves in all its components. The goal of the spanning star forest problem [12] is to find the maximum-size spanning star forest of a given graph. In this paper, we study this problem in c-dense graphs, where for c ∈ (0,1), a graph of n vertices is called c-dense if it contains at least cn 2/2 edges [2]. We design a (a</font >+(1-</font >a</font >)Ö</font >c-</font >e</font >)(\alpha+(1-\alpha)\sqrt{c}-\epsilon)-approximation algorithm for spanning star forest in c-dense graphs for any ε> 0, where a</font > = \frac193240\alpha=\frac{193}{240} is the best known approximation ratio of the spanning star forest problem in general graphs [3]. Thus, our approximation ratio outperforms the best known bound for this problem when dealing with c-dense graphs. We also prove that for any c ∈ (0,1), there is a constant ε = ε(c) > 0 such that approximating spanning star forest in c-dense graphs within a factor of 1 − ε is NP-hard. We then demonstrate that for weighted versions (both node- and edge- weighted) of this problem, we cannot get any approximation algorithm with strictly better performance guarantee in c-dense graphs than that of the best possible approximation algorithm for general graphs. Finally, we give strong hardness-of-approximation results for a closely related problem, the minimum dominating set problem, in c-dense graphs.
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.