Please use this identifier to cite or link to this item: https://doi.org/10.1137/070682150
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. https://doi.org/10.1137/070682150
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
URI: http://scholarbank.nus.edu.sg/handle/10635/102874
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.

SCOPUSTM   
Citations

19
checked on Jun 15, 2018

WEB OF SCIENCETM
Citations

15
checked on May 15, 2018

Page view(s)

34
checked on May 25, 2018

Google ScholarTM

Check

Altmetric


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