Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs

DOI10.1007/BF02523239zbMath0864.68049OpenAlexW2013772871MaRDI QIDQ2365177

Yanyan Li

Publication date: 9 June 1997

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02523239

zbMATH Keywords

Hamilton cyclesemicomplete bipartite digraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items

Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• An improved parallel algorithm for maximal matching
• Matching is as easy as matrix inversion
• A linear-time algorithm for finding Hamiltonian cycles in tournaments
• A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian
• The complexity of finding generalized paths in tournaments
• Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
• Parallel Merge Sort
• Parallel Prefix Computation
• Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments
• The Parallel Evaluation of General Arithmetic Expressions
• A simple parallel tree contraction algorithm
• A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments