# 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

##### MSC:
 05C38 Paths and cycles 05C45 Eulerian and Hamiltonian graphs 68R10 Graph theory (including graph drawing) in computer science 05C20 Directed graphs (digraphs), tournaments
##### Keywords:
polynomial algorithm; digraph; longest path; Hamiltonian path
Full Text: