A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

DOI10.1016/J.DISC.2008.02.041zbMATH Open1179.05107OpenAlexW2091936180MaRDI QIDQ1024477FDOQ1024477

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

parallel algorithmHamiltonian cycle

Mathematics Subject Classification ID

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

Cites Work

• Proof of the Seymour conjecture for large graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Proof of the Alon-Yuster conjecture
• Tripartite Ramsey numbers for paths
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some Theorems on Abstract Graphs
• Blow-up lemma
• Proof of a Packing Conjecture of Bollobás
• 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
• Title not available (Why is that?)
• A method in graph theory
• On the square of a Hamiltonian cycle in dense graphs
• On the number of Hamiltonian cycles in Dirac graphs
• An algorithmic version of the blow-up lemma
• Tripartite version of the Corrádi-Hajnal theorem
• Title not available (Why is that?)
• The Algorithmic Aspects of the Regularity Lemma
• Title not available (Why is that?)
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• Constructing a Maximal Independent Set in Parallel
• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
• Hypergraph Packing and Graph Embedding
• Parallel algorithms for finding Hamilton cycles in random graphs
• Fast parallel algorithms for finding hamiltonian paths and cycles in a tournament

Cited In (11)

• A space-efficient parameterized algorithm for the Hamiltonian Cycle problem by dynamic algebraization
• On prisms, Möbius ladders and the cycle space of dense graphs
• COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY
• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
• An Efficient Parallel Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs
• Hamilton cycles in dense vertex-transitive graphs
• Hamiltonicity, minimum degree and leaf number
• Title not available (Why is that?)
• Hamiltonian degree sequences in digraphs
• Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs

   Recommendations

• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs 👍 👎
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Fast parallel algorithms for finding hamiltonian paths and cycles in a tournament 👍 👎
• An Efficient Parallel Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs 👍 👎

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

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