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

@article{citeulike:1750669, abstract = {By making use of lexicographic breadth first search (Lex-BFS) and partition refinement with pivots, we obtain very simple algorithms for some well-known problems in graph theory. We give a O(n+mlogn) algorithm for transitive orientation of a comparability graph, and simple linear algorithms to recognize interval graphs, convex graphs, Y-semichordal graphs and matrices that have the consecutive ones property. Previous approaches to these problems used difficult preprocessing steps, such as computing PQ-trees or modular decomposition. The algorithms we give are easy to understand and straightforward to prove. They do not make use of sophisticated data structures, and the complexity analysis is straightforward.}, author = {Habib, Michel and Mcconnell, Ross and Paul, Christophe and Viennot, Laurent }, citeulike-article-id = {1750669}, comment = {http://en.wikipedia.org/wiki/Interval\_graph The original linear time recognition algorithm of Booth and Lueker (1976) is based on their complex PQ tree data structure, but Habib et al (2000) showed how to solve the problem more simply, based on the fact that a graph is an interval graph if and only if it is chordal and its complement is a comparability graph (Golumbic 1980). * Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000). "Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing". Theor. Comput. Sci. 234: 59–84. }, doi = {10.1016/S0304-3975(97)00241-7}, journal = {Theoretical Computer Science}, keywords = {algorithms, graph, testing}, month = {March}, number = {1-2}, pages = {59--84}, posted-at = {2007-10-10 14:49:35}, priority = {2}, title = {Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing}, url = {http://dx.doi.org/10.1016/S0304-3975(97)00241-7}, volume = {234}, year = {2000} }

TY - JOUR ID - citeulike:1750669 L3 - citeulike-article-id:1750669 TI - Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing JF - Theoretical Computer Science VL - 234 IS - 1-2 SP - 59 EP - 84 N2 - By making use of lexicographic breadth first search (Lex-BFS) and partition refinement with pivots, we obtain very simple algorithms for some well-known problems in graph theory. We give a O(n+mlogn) algorithm for transitive orientation of a comparability graph, and simple linear algorithms to recognize interval graphs, convex graphs, Y-semichordal graphs and matrices that have the consecutive ones property. Previous approaches to these problems used difficult preprocessing steps, such as computing PQ-trees or modular decomposition. The algorithms we give are easy to understand and straightforward to prove. They do not make use of sophisticated data structures, and the complexity analysis is straightforward. KW - algorithms KW - graph KW - testing N1 - http://en.wikipedia.org/wiki/Interval_graph The original linear time recognition algorithm of Booth and Lueker (1976) is based on their complex PQ tree data structure, but Habib et al (2000) showed how to solve the problem more simply, based on the fact that a graph is an interval graph if and only if it is chordal and its complement is a comparability graph (Golumbic 1980). * Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000). "Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing". Theor. Comput. Sci. 234: 59–84. AU - Habib, Michel AU - Mcconnell, Ross AU - Paul, Christophe AU - Viennot, Laurent PY - 2000/03/06/ UR - http://dx.doi.org/10.1016/S0304-3975(97)00241-7 ER -