An nc algorithm to recognize hhd-free graphs

Abstract

The HHD-free graphs are a class of perfect graphs that strictly contain the cographs, the chordal graphs, the Matula-perfect graphs, and the Welsh-Powell opposition graphs. In this paper we present two characterizations of the HHD-free graphs and show how to use them to produce a parallel recognition algorithm which runs in O(log n) time using O(n ⁴) processors on a concurrent-read, concurrent-write parallel random access machine.

Keywords:

• Chordal graphs
• HHD-free graphs
• parallel algorithms
• NC algorithms
• perfect graphs