A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs

A. Bretscher, D.G. Corneil, M. Habib, C. Paul, A simple linear time LexBFS cograph recognition algorithm—extended abstract, Proceedings of the 29th WG Workshop, Elspeet, The Netherlands, 2003, to appear.

J.-M. Chang, C.-W. Ho, M.-T. Ko, LexBFS-ordering in asteroidal triple-free graphs, in: A. Aggarwal, C. Pandu Rangan (Eds.), Proceedings of the ISAAC 99, 10th Symposium on Algorithms and Computation, Lectures Notes in Computer Science, Vol. 1741, Springer, Berlin, 1999, pp. 163–172.

Corneil, 1995, Simple linear time recognition of unit interval graphs, Inform. Process. Lett., 55, 99, 10.1016/0020-0190(95)00046-F

D.G. Corneil, S. Olariu, L. Stewart, The LBFS structure and recognition of interval graphs, in preparation; extended abstract appeared as The ultimate interval graph recognition algorithm?—extended abstract, in: Proceedings of SODA 98, Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, 1998, pp. 175–180.

Deng, 1996, Linear time representation algorithms for proper circular arc graphs and proper interval graphs, SIAM J. Comput., 25, 390, 10.1137/S0097539792269095

de Figueiredo, 1995, A linear-time algorithm for proper interval graph recognition, Inform. Process. Lett., 56, 179, 10.1016/0020-0190(95)00133-W

Golumbic, 1980

Habib, 2000, Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoret. Comput. Sci., 234, 59, 10.1016/S0304-3975(97)00241-7

P. Hell, J. Huang, Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs, manuscript, 2003.

Hell, 2001, A fully dynamic algorithm for recognizing and representing proper interval graphs, SIAM J. Comput., 31, 289, 10.1137/S0097539700372216

Korte, 1989, An incremental linear-time algorithm for recognizing interval graphs, SIAM J. Comput., 18, 68, 10.1137/0218005

D. Kratsch, R.M. McConnell, K. Mehlhorn, J.P. Spinrad, Certifying algorithms for recognizing interval graphs and permutation graphs, in: Proceedings of the SODA 03, 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, 2003, pp. 158–167.

J.-M. Lanlignel, Private communications, 1999.

Looges, 1993, Optimal greedy algorithms for indifference graphs, Comput. Math. Appl., 25, 15, 10.1016/0898-1221(93)90308-I

T. Ma, unpublished manuscript.

D. Meister, Recognizing and computing minimal triangulations efficiently, Technical Report 302, Fakultät für Mathematik und Informatik, Universität Würzburg, 2002.

Panda, 2003, A linear time recognition algorithm for proper interval graphs, Inform. Process. Lett., 87, 153, 10.1016/S0020-0190(03)00298-9

Roberts, 1969, Indifference graphs, 139

Roberts, 1971, On the compatibility between a graph and a simple order, J. Combin. Theory Ser. B, 11, 28, 10.1016/0095-8956(71)90010-4

Rose, 1976, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 266, 10.1137/0205021

K. Simon, A new simple linear algorithm to recognize interval graphs, in: H. Bieri, H. Noltemeyer (Eds.), Proceedings of the CG 91, International Workshop on Computational Geometry, Lectures Notes in Computer Science, Vol. 553, Springer, Berlin, 1992, pp. 289–308.

G. Wegner, Eigenschaften der nerven homologische-einfactor familien in Rn, Ph.D. Thesis, Universität Gottigen, Germany, 1967.