parallel Algorithms for Finding a Hamiltonian Path and a Hamiltonian Cycle in an In-Tournament Graph

摘要

As a super class of tournament digraphs, Bang- Jensen, Huang andPrisner 4 defined an in-tournament digraph (in-tournamemt forshort) and investigated a number of its nice properties, Thein-tournament is a directed graph in which the set of in-neighbors ofevery vertex induces a tournament digraph In other words, thepresence of arcs (x, z) and (y, z) implies that exactly one of (x, y)or (y, x) exists. In this paper, we propose, for in-tournaments,parallel algorithms for examining the exis- tence of a Hamiltonianpath and a Hamiltonian cycle and for constructing them, if theyexist.