A SAT based effective algorithm for the directed Hamiltonian cycle problem

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

Authors: Gerold Jäger, Weixiong Zhang 

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

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

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 (3)

• A space-efficient parameterized algorithm for the Hamiltonian Cycle problem by dynamic algebraization
• A successful algorithm for solving directed Hamiltonian path problems
• An effective algorithm for and phase transitions of the directed Hamiltonian cycle problem

Uses Software

• Concorde

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)