J. Alber, J. Gramm, J. Guo, and R. Niedermeier, Towards optimally solving the longest common subsequence problem for sequences with nested arc annotations in linear time An introduction to chordal graphs and clique trees, Proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching Graph Theory and Sparse Matrix Computation, p.129, 1993.

M. Halldorsson, J. Naor, H. Shachnai, and I. Shapira, Scheduling split intervals, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete AlgorithmsDGP88] I. Dagan, M.C. Golumbic, and R.Y. Pinter, Trapezoid graphs and their coloring, pp.732741-3546, 1988.

]. P. Eva99 and . Evans, Finding common subsequences with arcs and pseudoknots Incidence matrices and interval graphs, Proceedings of the 10th Annual Symposium Combinatorial Pattern Matching, pp.270280-835855, 1965.

R. [. Felsner, L. Müller, and . Wernisch, Trapezoid graphs and generalizations: Geometry and algorithms, 1332. [Fre75] M.L. Fredman, On computing the length of longest increasing subsequences, pp.11-2935, 1975.
DOI : 10.1007/3-540-58218-5_13
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.5459

J. [. Gramm, R. Guo, . D. Niedermeier-[-gip99-], S. Goldman, C. H. Istrail et al., Pattern matching for arcannotated sequences Algorithmic aspects of protein structure similarity Golumbic, Algorithmic graph theory and perfect graphs, Proceedings of the the 22nd Conference on Foundations of Software Technology and Theoretical Computer Science Lecture Notes in Computer Science Proceedings of the 40th Annual Symposium of Foundations of Computer Science (FOCS99), pp.182193-512522, 1979.

G. [. Jiang, B. Lin, K. Ma, and . Zhang, The longest common subsequence problem for arc-annotated sequences Determining DNA sequence similarity using maximum independent set algorithms for interval graphs, Proc. 11th Annual Symposium on Combinatorial Pattern Matching Proceedings of the Third Scandinavian Workshop on Algorithm Theory (SWAT 92), Lecture Notes in Computer Science, pp.154165-326337, 1992.

S. Micali and V. V. Vazirani, An O( p |V ||E|) algorithm for nding maximum matching in general graphs On double and multiple interval graphs, Proceedings of the 21st Annual Symposium on Foundation of Computer Science, pp.1727-205211, 1979.

M. [. Tarjan and . Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput, pp.13-566579, 1984.

]. V. Vaz94, . [. Vazirani, D. Viksna, and . Gilbert, A theory of alternating paths and blossoms for proving correctness of the O( p |V ||E|) maximum matching algorithm Pattern matching and pattern discovery algorithms for protein topologies [Via02] S. Vialette, Pattern matching over 2-intervals sets, Proc. 13th Annual Symposium Combinatorial Pattern Matching On the computational complexity of 2-interval pattern matching, pp.98111-5363, 1984.