zbMATH — the first resource for mathematics

Finding a longest path in a complete multipartite digraph. (English) Zbl 0773.05071
A digraph obtained by replacing each edge of a complete \(m\)-partite graph with an arc or a pair of mutually opposite arcs with the same end vertices is called a complete \(m\)-partite digraph. We describe an \(O(n^ 3)\) algorithm for finding a longest path in a complete \(m\)-partite \((m\geq 2)\) digraph with \(n\) vertices. The algorithm requires time \(O(n^{2.5})\) in case of testing only the existence of a Hamiltonian path and finding it if one exists. It is simpler than the algorithm of Y. Manoussakis and Z. Tuza [SIAM J. Discrete Math. 3, No. 4, 537-543 (1990; Zbl 0715.05042)], which works only for \(m=2\). Our algorithm implies a simple characterization of complete \(m\)-partite digraphs having Hamiltonian paths which was obtained for the first time in [the author, Kibernetika 1985, No. 4, 124-125 (1985; Zbl 0606.05029)] (for \(m=2)\) and in [the author, Kibernetika 1988, No. 1, 107-108 (1988; Zbl 0674.05047)] (for \(m\geq 2)\).
Reviewer: G.Gutin

05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
68R10 Graph theory (including graph drawing) in computer science
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI