Please use this identifier to cite or link to this item:
Title: Approximating the spanning star forest problem and its application to genomic sequence alignment
Authors: Thach, N.C.
Shen, J.
Hou, M.
Sheng, L.
Miller, W.
Zhang, L. 
Keywords: Approximation algorithm
Dominating set
Genomic sequence alignment
Spanning star forest
Issue Date: 2008
Citation: Thach, N.C., Shen, J., Hou, M., Sheng, L., Miller, W., Zhang, L. (2008). Approximating the spanning star forest problem and its application to genomic sequence alignment. SIAM Journal on Computing 38 (3) : 946-962. ScholarBank@NUS Repository.
Abstract: This paper studies the algorithmic issues of the spanning star forest problem. We prove the following results: (1) There is a polynomial-time approximation scheme for planar graphs; (2) there is a polynomial-time 3/5-approximation algorithm for graphs; (3) it is NP-hard to approximate the problem within ratio 259/260 + ε{lunate} graphs; (4) there is a linear-time algorithm to compute the maximum star forest of a weighted tree; (5) there is a polynomial-time 1/2-approximation algorithm for weighted graphs. We also show how to apply this spanning star forest model to aligning multiple genomic sequences over a tandem duplication region. © 2008 Society for Industrial and Applied Mathematics.
Source Title: SIAM Journal on Computing
ISSN: 00975397
DOI: 10.1137/070682150
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Dec 17, 2018


checked on Dec 17, 2018

Page view(s)

checked on Nov 9, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.