Parallel interval order recognition and construction of interval representations

AbstractParallel algorithms for recognizing and representing interval orders are proposed for different models of parallel random access machines (PRAM). The algorithms accept as input a transitively-closed directed graph with N nodes and M edges. They run in time O(log N) with O(N + M) processors and O(N + M) space and in constant time with O(N2) processors and O(N2) space depending on the data structure and the PRAM model used. Optimal probabilistic algorithms for PRAM are also presented as well as algorithms for distributed-memory machines