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.05049OpenAlexW2986504093MaRDI 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 cyclepolynomial algorithmmultipartite tournamentssemicomplete multipartite digraphscycle through specified vertices

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (14)

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

This page was built for publication: A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs