Conference proceeding
Approximating the Spanning Star Forest Problem and Its Applications to Genomic Sequence Alignment
PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, Vol.7-09-, pp.645-654
01 Jan 2007
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 unweighted graphs; (2) there is a polynomial-time algorithm with approximation ratio for unweighted graphs; (3) it is NP-hard to approximate the problem within ratio 545/546 + epsilon 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.
Metrics
3 Record Views
Details
- Title
- Approximating the Spanning Star Forest Problem and Its Applications to Genomic Sequence Alignment
- Creators
- C. Thach Nguyen - Natl Univ Spore, Dept Math, Singapore 117543, SingaporeJian ShenMinmei HouLi ShengWebb MillerLouxin Zhang - Natl Univ Spore, Dept Math, Singapore 117543, SingaporeSIAM/ACM
- Publication Details
- PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, Vol.7-09-, pp.645-654
- Conference
- EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 18th
- Publisher
- Siam
- Number of pages
- 4
- Grant note
- R-146-000-068-112 / NUS ARF CCR-0311413 / NSF; National Science Foundation (NSF) HG002238 / NIH; United States Department of Health & Human Services; National Institutes of Health (NIH) - USA
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Mathematics
- Identifiers
- 991019173535004721
UN Sustainable Development Goals (SDGs)
This output has contributed to the advancement of the following goals:
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Web of Science research areas
- Computer Science, Theory & Methods
- Mathematics, Applied