Parallel algorithms for finding a Hamiltonian path and a Hamiltonian cycle in an in-tournament graph

作     者：Nakayama, S Masuyama, S 

作者机构：Univ Tokushima Fac Integrated Arts & Sci Dept Math Sci Tokushima 7708502 Japan Toyohashi Univ Technol Dept Knowledge Based Informat Engn Toyohashi Aichi 4418580 Japan 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (IEICE Trans Fund Electron Commun Comput Sci)

年 卷 期：1998年第E81A卷第5期

页      面：757-767页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：parallel algorithms Hamiltonian path Hamiltonian cycle in-tournament 

摘      要：As a super class of tournament digraphs, Bang-Jensen, Huang and Prisner [4] defined an in-tournament digraph (in-toumament for short) and investigated a number of its nice properties. The in-tournament is a directed 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 constructing them, if they exist.