On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
DOI10.1006/JAGM.1993.1046zbMATH Open0782.68055OpenAlexW2079325521MaRDI QIDQ4275334FDOQ4275334
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
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
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)
Cited In (10)
- Hamilton cycles in hypergraphs below the Dirac threshold
- Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs
- An Efficient Parallel Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs
- A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
- Title not available (Why is that?)
- 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)
