A SAT based effective algorithm for the directed Hamiltonian cycle problem

DOI10.1007/978-3-642-13182-0_20MaRDI QIDQ3569745zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(6)

• A linear-size conversion of HCP to 3HCP
• Incremental SAT-based method with native Boolean cardinality handling for the Hamiltonian cycle problem
• FHCP challenge set: the first set of structurally difficult instances of the Hamiltonian cycle problem
• 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

Describes a project that uses

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)