Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
Abstract
Type
Type of the conference item
Journal type
peer reviewed
Educational material type
Conference Name
Journal name
Journal of Parallel and Distributed Computing
Book name
Book series
Book edition
Alternative title / Subtitle
Description
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 in 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 + in) 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 QT-graph 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. (C) 2003 Elsevier Inc. All rights reserved.
Description
Keywords
parallel algorithms, quasi-threshold graphs, recognition, tree representation, hamiltonian cycles, hamiltonian completion number, complexity, recognition algorithm, cographs
Subject classification
Citation
Link
Language
en
Publishing department/division
Advisor name
Examining committee
General Description / Additional Comments
Institution and School/Department of submitter
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής