A linear-time algorithm for finding Hamiltonian cycles in tournaments
type: Item
instance of: scholarly article
title: A linear-time algorithm for finding Hamiltonian cycles in tournaments
zbMATH Open document ID: 0776.05095
DOI: 10.1016/0166-218X(92)90233-Z
published in: Discrete Applied Mathematics
publication date: 1992-09-27T00:00:00Z
review text: The author presents an elegant algorithm for transforming a Hamilton path in an \(n\)-node tournament into a Hamiltonian cycle or into its strongly connected components, if there is no Hamiltonian cycle. Combined with a known \(O(n\log n)\) algorithm for determining a Hamiltonian path, it yields an algorithm runing in linear time with respect to the number \(m=n(n-1)/2\) of arcs which is an improvement of \(O(\log n)\) over the previously best known algorithm.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 61825
zbMATH Keywords: linear-time algorithm
zbMATH Keywords: Hamilton path
zbMATH Keywords: tournament
zbMATH Keywords: Hamiltonian cycle
author: Y. Manoussakis
reviewed by: Hartmut Schmeck
MaRDI profile type: Publication
cites work: Q3267901
cites work: The complexity of finding generalized paths in tournaments
cites work: Q4124858
cites work: Fast parallel algorithms for finding hamiltonian paths and cycles in a tournament
description: scientific article; zbMATH DE number 61825