loading...
Improved Efficient Parallel Algorithms to Recognize Interval Graphs and Interval Hypergraphs
Maui, Hawaii January 03-January 06
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/HICSS.1997.66721230th Hawaii International Conference ...
 This Article 
 
PURCHASE ARTICLE: $0
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Elias Dahlhaus, University of Bonn,
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
Usage of this product signifies your acceptance of the Terms of Use.