A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

DOI10.1016/J.DISC.2008.02.041MaRDI QIDQ1024477zbMATHOpenAlexFDO

Authors 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)

Recommendations

• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
• scientific article; zbMATH DE number 176753
• Fast parallel algorithms for finding hamiltonian paths and cycles in a tournament
• An Efficient Parallel Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs

Cites work

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

Cited in

(12)

• scientific article; zbMATH DE number 176753 (Why is no real title available?)
• On prisms, Möbius ladders and the cycle space of dense graphs
• Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
• Computational complexity of the perfect matching problem in hypergraphs with subcritical density
• Hamiltonian degree sequences in digraphs
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
• A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
• A space-efficient parameterized algorithm for the Hamiltonian Cycle problem by dynamic algebraization
• Hamiltonicity, minimum degree and leaf number
• An Efficient Parallel Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs
• Hamilton cycles in dense vertex-transitive 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)