×

Polynomial algorithms for finding cycles and paths in bipartite tournaments. (English) Zbl 0715.05042

The paper gives algorithms for finding Hamiltonian cycles in a bipartite tournament in \(O(n^{2.5})\) steps, for finding Hamiltonian paths in a bipartite tournament in \(O(n^{2.5})\) time, and for finding cycles through two specified nodes in a bipartite tournament in \(O(n^ 3)\) time, where n is the number of nodes of the bipartite tournament.
Reviewer: Wai-Kai Chen

MSC:

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