Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing

Berge, 1970

Booth, 1976, Testing for the consecutive ones property, interval graphs and graph planarity using pq-tree algorithm, J. Comput. System Sci., 13, 335, 10.1016/S0022-0000(76)80045-1

Brandstädt, 1991, Classes of bipartite graphs related to chordal graphs, Discrete Appl. Math., 32, 51, 10.1016/0166-218X(91)90023-P

Cournier, 1994, A new linear algorithm of modular decomposition, vol. 787, 68

E. Dahlhaus, J. Gustedt, R.M. McConnell, Efficient and practical modular decomposition, in: Proc. 7th Ann. ACM–SIAM Symp. on Discrete Algorithm, SIAM, Philadelphia, 1997, pp. 26–35.

P. Galinier, M. Habib, C. Paul, Chordal graphs and their clique graph, in: M. Nagl (Ed.), Graph-Theoretic Concepts in Computer Science, WG’95, Lecture Notes in Computer Science, vol. 1017, Aachen, Germany, June 1995, Proc. 21st Internat. Workshop WG’95, Springer, Berlin.

Gallai, 1967, Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar., 18, 25, 10.1007/BF02020961

Gavril, 1974, The intersection graphs of a path in a tree are exactly the chordal graphs, J. Combin. Theory, 16, 47, 10.1016/0095-8956(74)90094-X

Golumbic, 1980

Hsu, Ma, Substitution decomposition on chordal graphs and applications, in: Proc. 2nd ACM-SIGSAM Internat. Symp. on Symbolic Algebraic Comput., Lecture Notes in Computer Science, vol. 557, Springer, Berlin.

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

R.M. McConnell, J.P. Spinrad, Linear-time modular decomposition and efficient transitive orientation of comparability graphs, in: Proc. 5th Annual ACM–SIAM Symp. on Discrete Algorithms, Arlington, VA, 1994, pp. 536–545.

McConnell, 1997, Linear-time modular decomposition and efficient transitive orientation of undirected graphs, 19

Paige, 1987, Three partition refinement algorithms, SIAM J. Comput., 16, 973, 10.1137/0216062

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

J.P. Spinrad, Graph partitioning, 1986.