A POLYNOMIAL ALGORITHM FOR THE HAMILTONIAN CYCLE PROBLEM IN SEMICOMPLETE MULTIPARTITE DIGRAPHS

Authors
BANGJENSEN J GUTIN G YEO A
Citation
J. Bangjensen et al., A POLYNOMIAL ALGORITHM FOR THE HAMILTONIAN CYCLE PROBLEM IN SEMICOMPLETE MULTIPARTITE DIGRAPHS, Journal of graph theory, 29(2), 1998, pp. 111-132
Citations number
22
Categorie Soggetti
Mathematics,Mathematics
Journal title
Journal of graph theory → ACNP
ISSN journal
03649024
Volume
29
Issue
2
Year of publication
1998
Pages
111 - 132
Database
ISI
SICI code
0364-9024(1998)29:2<111:APAFTH>2.0.ZU;2-V
Abstract
We describe a polynomial algorithm for the Hamiltonian cycle problem f or semicomplete multipartite digraphs. The existence of such an algori thm 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 (1 995) 481-505). (C) 1998 John Wiley & Sons, Inc. J Graph Theory 29: 111 -132, 1998.