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

DOI10.1006/jagm.1993.1046zbMath0782.68055OpenAlexW2079325521MaRDI QIDQ4275334

Péter Hajnal, Elias Dahlhaus, 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

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

Related Items (6)

Regular-factors in the complements of partial k-trees ⋮ On the Parameterized Parallel Complexity and the Vertex Cover Problem ⋮ Approximation algorithms for bounded degree phylogenetic roots ⋮ Hamilton cycles in hypergraphs below the Dirac threshold ⋮ COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY ⋮ A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

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