Pattern Matching Problems over 2-Interval Sets

1. B. Billoud, M. Kontic, and A. Viari. Palingol: a declarative programming language to describe nucleic acids secondary structures and to scan sequence database. Nucl. Acids Res., 24:1395–403, 1996.

   Article  Google Scholar 

2. I. Dagan, M. C. Golumbic, and R. Y. Pinter. Trapezoid graphs and their coloring. Discrete Appl. Math., 21:35–46, 1988.

   Article  MATH  MathSciNet  Google Scholar 

3. P. Evans. Finding common subsequences with arcs and pseudoknots. In Proceedings of the 10th Annual Symposium Combinatorial Pattern Matching (CPM 1999), volume 1645 of Lecture Notes in Computer Science, pages 270–280, 1999.

   Chapter  Google Scholar 

4. S. Felsner, R. Müller, and L. Wernisch. Trapezoid graphs and generalizations: Geometry and algorithms. Discrete Appl. Math., 74:13–32, 1997.

   Article  MATH  MathSciNet  Google Scholar 

5. M. R. Garey and D. S. Johnson. Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, San Franciso, 1979.

   MATH  Google Scholar 

6. F. Gavril. Algorithms for a maximum clique and a minimum independent set of a circle graph. Networks, 3:261–273, 1973.

   Article  MATH  MathSciNet  Google Scholar 

7. D. Goldman, S. Istrail, and C. H. Papadimitriou. Algorithmic aspects of protein structure similarity. In IEEE Proceedings of the 40th Annual Conference of Foundations of Computer Science (FOCS99), pages 512–521, 1999.

   Google Scholar 

8. M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.

   MATH  Google Scholar 

9. U. I. Gupta, D. T. Lee, and J.Y-T. Leung. Efficient algorithms for interval graph and circular-arc graphs. Networks, 12:459–467, 1982.

   Article  MATH  MathSciNet  Google Scholar 

10. T. Jiang, G.-H. Lin, B. Ma, and K. Zhang. The longest common subsequence problem for arc-annotated sequences. In Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM 2000), volume 1848 of Lecture Notes in Computer Science, pages 154–165, 2000.

    Chapter  Google Scholar 

11. P. Kilpeläinen. Tree matching problems with applications to structured text databases. PhD thesis, University of Helsinki, Finland, 1992.

    Google Scholar 

12. E. L. Lawler and D. W. Wood. Branch and bound methods: A survey. Operations Research, 14:699–719, 1966.

    Article  MATH  MathSciNet  Google Scholar 

13. S. Vialette. Aspects algorithmiques de la pr’ediction des structures secondaires d’ARN. PhD thesis, Universit’e Denis Diderot, Paris, France, 2001. (in french).

    Google Scholar 

14. D. B. West and D. B. Shmoys. Recognizing graphs with fixed interval number is NP-complete. Discrete Appl. Math., 8:295–305, 1984.

    Article  MATH  MathSciNet  Google Scholar 

Download references