A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs

Bang-Jensen, J., Gutin, Gregory and Yeo, Anders

(1998)

Bang-Jensen, J., Gutin, Gregory and Yeo, Anders (1998) A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs. Journal of Graph Theory, 29 (2).

Our Full Text Deposits

Full text access: Open

Full Text - 235.41 KB

Links to Copies of this Item Held Elsewhere

Link to Publisher Copy

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).

Information about this Version

This is a Submitted version
This version's date is: 1998
This item is not peer reviewed

Link to this Version

https://repository.royalholloway.ac.uk/items/b56c62f3-55b8-6ede-d958-870f21e5f2c5/3/

Item TypeJournal Article
TitleA polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs
AuthorsBang-Jensen, J.
Gutin, Gregory
Yeo, Anders
Uncontrolled KeywordsHamiltonian cycle, polynomial algorithm, semicomplete multipartite digraph, multipartite tournament, cycle through specified vertices
DepartmentsFaculty of Science\Computer Science

Identifiers
doihttp://dx.doi.org/10.1002/(SICI)1097-0118(199810)29:2<111::AID-JGT7>3.0.CO;2-U

Deposited by Research Information System (atira) on 01-Jun-2012 in Royal Holloway Research Online.Last modified on 01-Jun-2012

Details