We present simple parallel algorithms to recognize hypergraphs with the property that the vertices can be ordered that the hyperedges form intervals. The algorithm circumvents P-Q-trees and is a simplification of the algorithm of Klein and Reif [12] This results to a simple parallel algorithm for interval graph recognition and for recognition of convex bipartite graphs. The basic ideas are quite similar to the interval graph recognition algorithm of Hsu. The major idea is that we can circumvent the lexical breadth-first search procedure. With similar techniques, also interval hypergraphs can be recognized. With a little bit less workload, interval hypergraphs can be recognized if a representation of the hyperedges as subtrees of a tree is known.
Citation:
Elias Dahlhaus, "Improved Efficient Parallel Algorithms to Recognize Interval Graphs and Interval Hypergraphs," hicss, vol. 1, pp.172, 30th Hawaii International Conference on System Sciences (HICSS) Volume 1: Software Technology and Architecture, 1997