New sequential and parallel algorithms for interval graph recognition (Q922725)

The paper aims at solving the problem of recognising interval graphs and at constructing an internal representation for interval graphs. The importance of this problem arises from the fact that many NP-complete graph problems admit polynomial time solutions if the input is restricted to the class of interval graphs. The algorithm proposed by the authors can be parallelized. Step 1 takes \(O(\log^ 3(n))\) time on \(n^ 4\) processors, step 2 takes O(log(n)) time using \(O(n^ 2)\) processors and step 3 takes O(log(n)) time using \(O(n^ 2)\) processors under the CREW model.