Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(6)
Approximate Algorithm
Dominating Set
Hardness of Approximation
Minimum Dominating Set
Star Graph
Weighted Graph
Subscribe
Academic
Publications
Improved Approximation Algorithms for the Spanning Star Forest Problem
Improved Approximation Algorithms for the Spanning Star Forest Problem,10.1007/9783540742081_4,Ning Chen,Roee Engelberg,C. Thach Nguyen,Prasad Rag
Edit
Improved Approximation Algorithms for the Spanning Star Forest Problem
(
Citations: 5
)
BibTex

RIS

RefWorks
Download
Ning Chen
,
Roee Engelberg
,
C. Thach Nguyen
,
Prasad Raghavendra
,
Atri Rudra
,
Gyanit Singh
A
star graph
is a tree of diameter at most two. A star forest is a graph that consists of nodedisjoint 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.71approximation algorithm for this problem, improving upon the approximation factor of 0.6 of Nguyen et al. (9). We also present a 0.64approximation algorithm for the problem on nodeweighted graphs. Finally, we present improved
hardness of approximation
results for the weighted versions of the problem.
Conference:
Approximation Algorithms for Combinatorial Optimization  APPROX
, pp. 4458, 2007
DOI:
10.1007/9783540742081_4
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.cs.technion.ac.il
)
(
www3.ntu.edu.sg
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
(
www.cs.washington.edu
)
More »
Citation Context
(1)
...Chen et.al. [
8
] improved the factor of unweighted MSSF to 0:71 and introduced nodeweighted MSSF giving a 0:64 factor algorithm for it. They also give a 31=32 and 19=20 hardness for the nodeweighted and edgeweighted MSSF problems...
Deeparnab Chakrabarty
,
et al.
On the Approximability of Budgeted Allocations and Improved Lower Boun...
References
(10)
The Probabilistic Method
(
Citations: 2202
)
Noga Alon
,
Joel Spencer
Published in 1992.
On the Approximation of Computing Evolutionary Trees
(
Citations: 9
)
Vincent Berry
,
Sylvain Guillemot
,
François Nicolas
,
Christophe Paul
Conference:
Computing and Combinatorics  COCOON
, pp. 115125, 2005
On the hardness of approximating minimization problems
(
Citations: 534
)
Carsten Lund
,
Mihalis Yannakakis
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 286293, 1993
Approximating the spanning star forest problem and its applications to genomic sequence alignment
(
Citations: 6
)
C. Thach Nguyen
,
Jian Shen
,
Minmei Hou
,
Li Sheng
,
Webb Miller
,
Louxin Zhang
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 645654, 2007
Some optimal inapproximabiity results
(
Citations: 64
)
J. H Astad
Published in 1997.
Sort by:
Citations
(5)
An Improved Approximation Algorithm for Spanning Star Forest in Dense Graphs
Jing He
,
Hongyu Liang
Conference:
Conference on Combinatorial Optimization and Applications  COCOA
, pp. 160169, 2010
An Improved Approximation Bound for Spanning Star Forest and Color Saving
(
Citations: 2
)
Stavros Athanassopoulos
,
Ioannis Caragiannis
,
Christos Kaklamanis
,
Maria Kyropoulou
Conference:
Mathematical Foundations of Computer Science  MFCS
, pp. 90101, 2009
Approximating the Spanning kTree Forest Problem
Chungshou Liao
,
Louxin Zhang
Conference:
Frontiers in Algorithmics  FAW
, pp. 293301, 2009
On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
(
Citations: 16
)
Deeparnab Chakrabarty
,
Gagan Goel
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 39, no. 6, pp. 687696, 2008
ALGORITHMS FOR BUDGETED AUCTIONS AND MULTIAGENT COVERING PROBLEMS
Gagan Goel