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

DOI<111::AID-JGT7>3.0.CO;2-U 10.1002/(SICI)1097-0118(199810)29:2<111::AID-JGT7>3.0.CO;2-UzbMath0916.05049MaRDI QIDQ4242916

Gregory Gutin, Anders Yeo, Jörgen Bang-Jensen

Publication date: 7 July 1999

Full work available at URL: https://doi.org/10.1002/(sici)1097-0118(199810)29:2<111::aid-jgt7>3.0.co;2-u

zbMATH Keywords

Hamiltonian cycle; polynomial algorithm; multipartite tournaments; semicomplete multipartite digraphs; cycle through specified vertices

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

05C45: Eulerian and Hamiltonian graphs

Related Items

Sparse Spanning $k$-Connected Subgraphs in Tournaments, Hamiltonicity, pancyclicity, and full cycle extendability in multipartite tournaments, Minimum cycle factors in quasi-transitive digraphs, Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs, Quasi-Hamiltonicity: A series of necessary conditions for a digraph to be Hamiltonian, Orientations of digraphs almost preserving diameter, Classification of de Bruijn-based labeled digraphs, Hamiltonian paths containing a given arc, in almost regular bipartite tournaments, Quasi-hamiltonian paths in semicomplete multipartite digraphs, Properly colored cycles in edge-colored complete graphs without monochromatic triangle: a vertex-pancyclic analogous result, Multipartite tournaments: a survey, On a cyclic connectivity property of directed graphs, Semicomplete Multipartite Digraphs, Cycles with a given number of vertices from each partite set in regular multipartite tournaments