Journal
THEORETICAL COMPUTER SCIENCE
Volume 234, Issue 1-2, Pages 59-84Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/S0304-3975(97)00241-7
Keywords
algorithm; data-structure; partition refinement; graph; Boolean matrix
Categories
Ask authors/readers for more resources
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 + m log n) 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. (C) 2000 Elsevier Science B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available