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

By making use of lexicographic breadth first search (Lex-BFS) and partition refinement with pivots, we obtain very simple algorithms for some well-kno wn problems in graph theory. We give a O(n + m log n) algorithm for transitive orientation of a comparab ility graph, and simple linear algorithms to recognize interval graphs, con vex graphs, Y-semichordal graphs and matrices that have the consecutive one s property. Previous approaches to these problems used difficult preprocessing steps, s uch as computing PQ-trees or modular decomposition. The algorithms we give are easy to understand and straightforward to prove. They do not make use o f sophisticated data structures, and the complexity analysis is straightfor ward. (C) 2000 Elsevier Science B.V. All rights reserved.