Premium
A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs
Author(s) -
Bang–Jensen Jørgen,
Gutin Gregory,
Yeo Anders
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199810)29:2<111::aid-jgt7>3.0.co;2-u
Subject(s) - multipartite , mathematics , combinatorics , hamiltonian path , hamiltonian path problem , hamiltonian (control theory) , graph , discrete mathematics , graph theory , mathematical optimization , quantum , quantum mechanics , physics , quantum entanglement
We describe a polynomial algorithm for the Hamiltonian cycle problem for semicomplete multipartite digraphs. The existence of such an algorithm was conjectured in G. Gutin, Paths and cycles in digraphs. Ph. D. thesis, Tel Aviv Univ., 1993. (see also G. Gutin, J Graph Theory 19 (1995) 481–505). © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 111–132, 1998