×

zbMATH — the first resource for mathematics

A polynomial algorithm for Hamiltonian-connectedness in semicomplete digraphs. (English) Zbl 0749.68057
Summary: We describe a polynomial algorithm, which either finds a Hamiltonian path with prescribed initial and terminal vertices in a tournament (in fact, in any semicomplete digraph), or decides that no such path exists.

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI