Approximating the 2-Interval Pattern Problem - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2005

Approximating the 2-Interval Pattern Problem

Résumé

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.
Fichier principal
Vignette du fichier
2-Interval.pdf (152.04 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00619979 , version 1 (20-03-2013)

Identifiants

  • HAL Id : hal-00619979 , version 1

Citer

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⟩
172 Consultations
358 Téléchargements

Partager

Gmail Facebook X LinkedIn More