|
|||||
|
|
A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs |
|
| Authors: | Jrgen Bang&#x;Jensen Gregory Gutin Anders Yeo |
| Abstract: | 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 |
| Keywords: | Hamiltonian cycle polynomial algorithm semicomplete multipartite digraph multipartite tournament cycle through specified vertices |