A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

DOI10.1016/J.DISC.2008.02.041zbMath1179.05107OpenAlexW2091936180MaRDI QIDQ1024477

Gábor N. Sárközy

Publication date: 17 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.02.041

zbMATH Keywords

Hamiltonian cycleparallel algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Vertex degrees (05C07)

Related Items (5)

Hamiltonicity, minimum degree and leaf number ⋮ On prisms, Möbius ladders and the cycle space of dense graphs ⋮ Hamilton cycles in dense vertex-transitive graphs ⋮ Hamiltonian degree sequences in digraphs ⋮ COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel algorithms for finding Hamilton cycles in random graphs
• A method in graph theory
• Proof of the Seymour conjecture for large graphs
• Blow-up lemma
• Tripartite version of the Corrádi-Hajnal theorem
• On the number of Hamiltonian cycles in Dirac graphs
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• Tripartite Ramsey numbers for paths
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• Fast parallel algorithms for finding hamiltonian paths and cycles in a tournament
• An algorithmic version of the blow-up lemma
• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
• The Algorithmic Aspects of the Regularity Lemma
• Hypergraph Packing and Graph Embedding
• Constructing a Maximal Independent Set in Parallel
• Proof of a Packing Conjecture of Bollobás
• On the square of a Hamiltonian cycle in dense graphs
• Some Theorems on Abstract Graphs
• Proof of the Alon-Yuster conjecture

This page was built for publication: A fast parallel algorithm for finding Hamiltonian cycles in dense graphs