Name
Title | ||
|---|---|---|
Approximating the spanning star forest problem and its applications to genomic sequence alignment |
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 unweighted graphs; (2) there is a polynomial-time algorithm with approximation ratio 3/5 for unweighted graphs; (3) it is NP-hard to approximate the problem within ratio 545/546 + ε for unweighted graphs; (4) there is a linear-time algorithm to compute the maximum star forest of a weighted tree; (5) there is a polynomial-time algorithm with approximation ratio 1/2 for weighted graphs. We also show how to apply this spanning star forest model to aligning multiple genomic sequences over a tandem duplication region. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/070682150 | SIAM Journal on Computing |
Keywords | Field | DocType |
approximation algorithm,dominating set,genome sequence | Sequence alignment,Graph,Discrete mathematics,Combinatorics,Multicast scheduling,Computer science,Planar | Journal |
Volume | Issue | ISSN |
38 | 3 | 0097-5397 |
Citations | PageRank | References |
14 | 0.86 | 15 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| C. Thach Nguyen | 1 | 114 | 8.69 |
| Jian Shen | 2 | 14 | 0.86 |
| Minmei Hou | 3 | 20 | 2.74 |
| Li Sheng | 4 | 14 | 0.86 |
| W Miller | 5 | 1301 | 295.71 |
| Louxin Zhang | 6 | 890 | 96.47 |