On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs

DOI10.1006/JAGM.1993.1046MaRDI QIDQ4275334zbMATH OpenOpenAlexFDO

Authors Elias Dahlhaus, Péter Hajnal, Marek Karpinski

Publication date 13 March 1994

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

Full work available at URL https://doi.org/10.1006/jagm.1993.1046

zbMATH Keywords

matchingHamiltonian cycledense graphsCREW-PRAMlinear number of processors

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs
• scientific article; zbMATH DE number 176753
• A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
• On the parallel complexity of the alternating Hamiltonian cycle problem
• Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs

Cited in

(10)

• Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs
• Hamilton cycles in hypergraphs below the Dirac threshold
• An Efficient Parallel Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs
• A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
• scientific article; zbMATH DE number 176753 (Why is no real title available?)
• Regular-factors in the complements of partial k-trees
• Approximation algorithms for bounded degree phylogenetic roots
• A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments
• Computational complexity of the perfect matching problem in hypergraphs with subcritical density
• On the parameterized parallel complexity and the vertex cover problem

This page was built for publication: On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs

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