PARALLEL ALGORITHMS FOR CONNECTIVITY PROBLEMS ON INTERVAL-GRAPHS

In this paper O(log log n) time parallel algorithms with linear work h ave been obtained on COMMON (or TOLERANT) CRCW PRAM for finding connec ted and biconnected components of an interval graph; assuming that int ervals are given in sorted (or pad-sorted) order. The algorithms take O(log n) time (with linear work) on a tree machine. k-connectivity of an interval graph can be tested and disconnecting sets found in O(k lo g log n) and O(k log n) time on a CRCW PRAM and Tree machine (respecti vely). In case the end-points are integers in range 1...n(O(1)), the a lgorithms use linear work and take O(k log() n) time on PRIORITY writ e PRAM and O(log log log n) time on TOLERANT or COMMON PRAM. In this c ase, the assumption that end-points are sorted can be done away with, at cost of randomisation.