Approximating the 2-Interval Pattern Problem

Abstract : We address the problem of approximating the 2-Interval Pattern problem over its various models and restrictions. This problem, which is motivated by RNA secondary structure prediction, asks to find a maximum cardinality subset of a 2-interval set with respect to some prespecified model. For each such model, we give varying approximation quality depending on the different possible restrictions imposed on the input 2-interval set.
Document type :
Conference papers
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619979
Contributor : Stéphane Vialette <>
Submitted on : Wednesday, March 20, 2013 - 6:59:34 PM
Last modification on : Wednesday, May 23, 2018 - 3:44:02 PM
Long-term archiving on : Friday, June 21, 2013 - 2:50:10 AM

File

2-Interval.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619979, version 1

Collections

Citation

Maxime Crochemore, Danny Hermelin, Gad M. Landau, Stéphane Vialette. Approximating the 2-Interval Pattern Problem. 13th Annual European Symposium on Algorithms (ESA'05), 2005, Mallorca, Spain, Spain. pp.426-437. ⟨hal-00619979⟩

Share

Metrics

Record views

364

Files downloads

223