Fast parallel algorithms for finding hamiltonian paths and cycles in a tournament

DOI10.1016/0196-6774(88)90042-9MaRDI QIDQ3786504zbMATHOpenAlexFDO

Authors Danny Soroker

Publication date 1988

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(88)90042-9

zbMATH Keywords

parallel algorithmHamiltonian cycleHamiltonian pathdirected graphtournamentstrongly connected components

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs
• A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments
• An Efficient Parallel Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs
• A linear-time algorithm for finding Hamiltonian cycles in tournaments
• Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs

Cited in

(16)

• The watchman's walk problem on directed graphs
• A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments
• Polynomial Algorithms for Finding Cycles and Paths in Bipartite Tournaments
• Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs
• Antidirected Hamiltonian paths between specified vertices of a tournament
• A linear-time algorithm for finding Hamiltonian cycles in tournaments
• NC algorithms for antidirected hamiltonian paths and cycles in tournaments
• Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments
• ON COST-OPTIMAL MERGE OF TWO INTRANSITIVE SORTED SEQUENCES
• Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey
• Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs
• A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
• Finding the maximum multi improvement on neighborhood exploration
• Finding an antidirected Hamiltonian path starting with a forward arc from a given vertex of a tournament
• A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs
• The Hamilton circuit problem on grids

This page was built for publication: Fast parallel algorithms for finding hamiltonian paths and cycles in a tournament

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3786504)