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-known problems in graph theory. We give a O(n+m logn) algorithm for transitive orientation of a comparability graph, and simple linear algorithms to reco...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2000-03, Vol.234 (1), p.59-84
Main Authors: Habib, Michel, McConnell, Ross, Paul, Christophe, Viennot, Laurent
Format: Article
Language:English
Subjects:
Algorithm
Applied sciences
Boolean matrix
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Data processing. List processing. Character string processing
Data-structure
Exact sciences and technology
Graph
Graph theory
Information retrieval. Graph
Mathematics
Memory organisation. Data processing
Partition refinement
Sciences and techniques of general use
Software
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 logn) 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(97)00241-7