Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
✍ Scribed by Michel Habib; Ross McConnell; Christophe Paul; Laurent Viennot
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 476 KB
- Volume
- 234
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
By making use of lexicographic breadth ÿrst search (Lex-BFS) and partition reÿnement 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 di cult 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.