A SAT based effective algorithm for the directed Hamiltonian cycle problem

DOI10.1007/978-3-642-13182-0_20zbMATH Open1284.05292OpenAlexW1529355251MaRDI QIDQ3569745FDOQ3569745

Weixiong Zhang, Gerold Jäger

Publication date: 22 June 2010

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13182-0_20

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cited In (2)

• A space-efficient parameterized algorithm for the Hamiltonian Cycle problem by dynamic algebraization
• A successful algorithm for solving directed Hamiltonian path problems

Uses Software

• Concorde

   Recommendations

• An effective algorithm for and phase transitions of the directed Hamiltonian cycle problem 👍 👎
• Incremental SAT-Based Method with Native Boolean Cardinality Handling for the Hamiltonian Cycle Problem 👍 👎
• An algorithm for finding hamilton cycles in random directed graphs 👍 👎
• A successful algorithm for solving directed Hamiltonian path problems 👍 👎
• A note on exploiting the Hamiltonian cycle problem substructure of the asymmetric traveling salesman problem 👍 👎

This page was built for publication: A SAT based effective algorithm for the directed Hamiltonian cycle problem

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