FINDING A LONGEST PATH IN A COMPLETE MULTIPARTITE DIGRAPH

A digraph obtained by replacing each edge of a complete m-partite grap h with an arc or a pair of mutually opposite arcs with the same end ve rtices is called a complete m-partite digraph. An O(n3) algorithm for finding a longest path in a complete m-partite (m greater-than-or-equa l-to 2) digraph with n vertices is described in this paper. The algori thm requires time O(n2.5) in case of testing only the existence of a H amiltonian path and finding it if one exists. It is simpler than the a lgorithm of Manoussakis and Tuza [SIAM J. Discrete Math., 3 (1990), pp . 537-543], which works only for m = 2. The algorithm implies a simple characterization of complete m-partite digraphs having Hamiltonian pa ths that was obtained for the first time in Gutin [Kibernetica (Kiev), 4 (1985), pp. 124-125] for m = 2 and in Gutin [Kibernetica (Kiev), 1 (1988), pp. 107-1081 for m greater-than-or-equal-to 2.