Parallel algorithms for Hamiltonian problems on quasi-threshold graphs

In this paper we show structural and algorithmic properties on the class of quasi-threshold graphs, or QT-graphs for short, and prove necessary and sufficient conditions for a QT-graph to be Hamiltonian. Based on these properties and conditions, we construct an efficient parallel algorithm for finding a Hamiltonian cycle in a QT-graph; for an input graph on n vertices and m edges, our algorithm takes Oðlog nÞ time and requires Oðn þ mÞ processors on the CREW PRAM model. In addition, we show that the problem of recognizing whether a QT-graph is a Hamiltonian graph and the problem of computing the Hamiltonian completion number of a nonHamiltonian QT-graph can also be solved in Oðlog nÞ time with Oðn þ mÞ processors. Our algorithms rely on Oðlog nÞ-time parallel algorithms, which we develop here, for constructing tree representations of a QT-graph; we show that a QTgraph G has a unique tree representation, that is, a tree structure which meets the structural properties of G: We also present parallel algorithms for other optimization problems on QT-graphs which run in Oðlog nÞ time using a linear number of processors