New Results for the 2-Interval Pattern Problem

Abstract : We present new results concerning the problem of finding a constrained pattern in a set of 2-intervals. Given a set of n 2-intervals D and a model R describing if two disjoint 2-intervals can be in precedence order ($<$), be allowed to nest ($\sqsubset$) and/or be allowed to cross $(\between$), we consider the problem of finding a maximum cardinality subset $\D' \subseteq \D$ of disjoint $2$-intervals such that any two $2$-intervals in $\D'$ agree with $R$. We improve the time complexity of the best known algorithm for $R = \{\sqsubset\}$ by giving an optimal O(n log n) time algorithm. Also, we give a graph-like relaxation for $R = \{\sqsubset,\between\}$ that is solvable in $O(n^2 \sqrt{n})$ time. Finally, we prove that the problem is NP-complete for $R = \{<,\between\}$ and in addition to that, we give a fixed-parameter tractability result based on the crossing structure of D.
Type de document :
Communication dans un congrès
Sahinalp Suleyman Cenk and Muthukrishnan S. and Dogrusoz Ugur. 15th Symposium on Combinatorial Pattern Matching (CPM'04), Jul 2004, Istanbul, Turkey, Turkey. Springer-Verlag, 3109, pp.311-322, 2004, LNCS
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-00620366
Contributeur : Guillaume Blin <>
Soumis le : vendredi 30 septembre 2011 - 15:32:06
Dernière modification le : mercredi 23 mai 2018 - 15:44:02
Document(s) archivé(s) le : samedi 31 décembre 2011 - 02:21:34

Fichier

hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00620366, version 1

Citation

Guillaume Blin, Guillaume Fertin, Stéphane Vialette. New Results for the 2-Interval Pattern Problem. Sahinalp Suleyman Cenk and Muthukrishnan S. and Dogrusoz Ugur. 15th Symposium on Combinatorial Pattern Matching (CPM'04), Jul 2004, Istanbul, Turkey, Turkey. Springer-Verlag, 3109, pp.311-322, 2004, LNCS. 〈hal-00620366〉

Partager

Métriques

Consultations de la notice

293

Téléchargements de fichiers

107