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

DOI10.1016/0196-6774(88)90042-9zbMATH Open0644.05036OpenAlexW2066708286MaRDI QIDQ3786504FDOQ3786504

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

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

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)

Cited In (15)

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

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)