Improved efficient parallel algorithms to recognize interval graphs and interval hypergraphs
Elias Dahlhaus · 2002
Presents simple parallel algorithms to recognize hypergraphs with the property that the vertices can be ordered so that the hyperedges form intervals. The algorithm circumvents P-Q-trees and is a simplification of the algorithm of Klein and Reif (1988). This results in a simple parallel algorithm for interval graph recognition and for the recognition of convex bipartite graphs. The basic ideas are quite similar to the interval graph recognition algorithm of Hsu (1992). The major idea is that we can circumvent the lexical breadth-first search procedure. With similar techniques, interval hypergraphs can also be recognized. They can be recognized with a slightly smaller workload if a representation of the hyperedges as subtrees is known.