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 and Prisne r [4] defined an in-tournament digraph (in-toumament for short) and in vestigated a number of its nice properties. The in-tournament is a dir ected graph in which the set of in-neighbors of every vertex induces a tournament digraph. In other words, the presence of arcs (x,z) and (y ,z) implies that exactly one of (x,y) or (y,z) exists. In this paper, we propose, for in-tournaments, parallel algorithms for examining the existence of a Hamiltonian path and a Hamiltonian cycle and for constr ucting them, if they exist.