×

zbMATH — the first resource for mathematics

A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs. (English) Zbl 0916.05049
A semicomplete multipartite digraph is a digraph whose vertices can be partitioned into a number \(k \geq 2\) of subsets (called colour classes) such that every pair of vertices from the same colour class are nonadjacent and every pair of vertices from different colour classes are adjacent (i.e., there is at least one arc between them). The paper provides a polynomial algorithm for the Hamiltonian cycle problem for semicomplete multipartite digraphs.

MSC:
05C45 Eulerian and Hamiltonian graphs
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI