Parallel Algorithms For Maximum Matching And Other Problems On Interval Graphs

Abstract

In this paper, we consider parallel algorithms on interval graphs. An interval graph is a graph having a one-to-one correspondence with a sequence of intervals on the real line, such that each vertex maps to an interval in the sequence and an edge exists between two vertices if and only if the corresponding intervals overlap. Throughout the paper we use the CREW PRAM model. Our main result is an $O(\log^{2} n)$ time, $O(n^{6}/\log n)$ processor algorithm for maximum matching on interval graphs. We give PT-optimal algorithms for maximum weighted clique, maximum independent set, minimum clique cover, and minimum dominating set for representations of interval graphs; and Hamiltonian circuit for representations of proper interval graphs. We also give an improved algorithm for minimum bandwidth on representations of proper interval graphs. In addition, we present $O (\log n)$ time, $O (n^{2}/\log n)$ processor algorithms for depth-first search on representations of interval graphs and maximum matching on representations of proper interval graphs.