Journal article
Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
SIAM journal on computing, v 38(3), pp 946-962
01 Jan 2008
Featured in Collection : UN Sustainable Development Goals @ Drexel
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 $\frac{3}{5}$-approximation algorithm for graphs; (3) it is NP-hard to approximate the problem within ratio $\frac{259}{260} + \epsilon$ for graphs; (4) there is a linear-time algorithm to compute the maximum star forest of a weighted tree; (5) there is a polynomial-time $\frac{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.
Metrics
Details
- Title
- Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
- Creators
- C. Thach Nguyen - ncthach@cs.washington.eduJian Shen - js48@txstate.eduMinmei Hou - mhou@cs.niu.eduLi Sheng - lsheng@math.drexel.eduWebb Miller - webb@bx.psu.eduLouxin Zhang - matzlx@nus.edu.sg
- Publication Details
- SIAM journal on computing, v 38(3), pp 946-962
- Publisher
- Society for Industrial and Applied Mathematics
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000258895100009
- Scopus ID
- 2-s2.0-55249086760
- Other Identifier
- 991019168651604721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Theory & Methods
- Mathematics, Applied