Optimal parallel algorithms for cut vertices, bridges, and Hamiltonian path in bounded interval tolerance graphs

We present parallel algorithms to find cut vertices, bridges, and Hamiltonian Path in bounded interval tolerance graphs. For a graph with n vertices, the algorithms require O(log n) time and use O(n) processors to run on Concurrent Read Exclusive Write Parallel RAM (CREW PRAM) model of computation. Our approach transforms the original graph problem to a problem in computational geometry. The total work done by the parallel algorithms is comparable to the work done by the best known sequential algorithms for the more restricted class of graphs, namely, interval graphs and permutation graphs. In this sense our algorithms have optimal complexity