**Finding a longest path in a complete multipartite digraph.** / Gutin, Gregory.

Research output: Contribution to journal › Article

Published

**Finding a longest path in a complete multipartite digraph.** / Gutin, Gregory.

Research output: Contribution to journal › Article

Gutin, G 1993, 'Finding a longest path in a complete multipartite digraph', *SIAM Journal on Discrete Mathematics*, vol. 6, no. 2, pp. 270-273. <http://epubs.siam.org/SIDMA/>

Gutin, G. (1993). Finding a longest path in a complete multipartite digraph. *SIAM Journal on Discrete Mathematics*, *6*(2), 270-273. http://epubs.siam.org/SIDMA/

Gutin G. Finding a longest path in a complete multipartite digraph. SIAM Journal on Discrete Mathematics. 1993;6(2):270-273.

@article{ef77839eb86b4c2a9008f11a7373e6eb,

title = "Finding a longest path in a complete multipartite digraph",

abstract = "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. An $O ( n^3 )$ algorithm for finding a longest path in a complete $m$-partite $( m \geq 2 )$ digraph with $n$ vertices is described in this paper. 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 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 paths 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–108] for $ m \geq 2 $.",

keywords = "digraph, longest path, polynomial algorithm",

author = "Gregory Gutin",

year = "1993",

language = "English",

volume = "6",

pages = "270--273",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Finding a longest path in a complete multipartite digraph

AU - Gutin, Gregory

PY - 1993

Y1 - 1993

N2 - 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. An $O ( n^3 )$ algorithm for finding a longest path in a complete $m$-partite $( m \geq 2 )$ digraph with $n$ vertices is described in this paper. 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 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 paths 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–108] for $ m \geq 2 $.

AB - 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. An $O ( n^3 )$ algorithm for finding a longest path in a complete $m$-partite $( m \geq 2 )$ digraph with $n$ vertices is described in this paper. 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 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 paths 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–108] for $ m \geq 2 $.

KW - digraph

KW - longest path

KW - polynomial algorithm

M3 - Article

VL - 6

SP - 270

EP - 273

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 2

ER -