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

In: SIAM Journal on Discrete Mathematics, Vol. 6, No. 2, 1993, p. 270-273.

Research output: Contribution to journalArticle

Published

Standard

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

In: SIAM Journal on Discrete Mathematics, Vol. 6, No. 2, 1993, p. 270-273.

Research output: Contribution to journalArticle

Harvard

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/>

APA

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/

Vancouver

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

Author

Gutin, Gregory. / Finding a longest path in a complete multipartite digraph. In: SIAM Journal on Discrete Mathematics. 1993 ; Vol. 6, No. 2. pp. 270-273.

BibTeX

@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",

}

RIS

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 -