
Summary: We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is \(O(\log n)\) using \(O(n^2/\log n)\) processors on a CRCW PRAM, and \(O(\log n \log \log n)\) on an EREW PRAM using \(O(n^2/ \log n \log \log n)\) processors. As a corollary, we obtain a new parallel algorithm for computing Hamiltonian cycles in tournaments. This algorithm can be implemented in time \(O(\log n)\) using \(O(n^2/\log n)\) processors in the CRCW model and in time \(O(\log^2 n)\) with \(O(n^2/\log n\log n)\) processors in the EREW model.
Graph theory (including graph drawing) in computer science, Analysis of algorithms and problem complexity, Distributed algorithms, Paths and cycles, Hamiltonian cycles, tournaments, Hamiltonian paths
Graph theory (including graph drawing) in computer science, Analysis of algorithms and problem complexity, Distributed algorithms, Paths and cycles, Hamiltonian cycles, tournaments, Hamiltonian paths
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
