Incremental SAT-Based Method with Native Boolean Cardinality Handling for the Hamiltonian Cycle Problem

DOI10.1007/978-3-319-11558-0_52zbMath1432.68420OpenAlexW27905376MaRDI QIDQ2938540

Mutsunori Banbara, Stéphanie Roussel, Naoyuki Tamura, Takehide Soh, Daniel Le Berre

Publication date: 14 January 2015

Published in: Logics in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-11558-0_52

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational aspects of satisfiability (68R07)

Related Items (5)

Combining SAT solvers with computer algebra systems to verify combinatorial conjectures ⋮ MathCheck: A Math Assistant via a Combination of Computer Algebra Systems and SAT Solvers ⋮ Concise integer linear programming formulation for clique partitioning problems ⋮ An incremental SAT-based approach for solving the real-time taxi-sharing service problem ⋮ Chinese remainder encoding for Hamiltonian cycles

Uses Software

• TSPLIB
• Sat4j
• Scarab
• Lynx

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity-sensitive decision procedures for abstract argumentation
• A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem
• The traveling salesman problem: An overview of exact and approximate algorithms
• Advances on the Hamiltonian problem -- a survey
• SAT problems with chains of dependent variables
• Recent advances on the Hamiltonian problem: survey III
• Solving QBF with Counterexample Guided Refinement
• An Effective Algorithm for and Phase Transitions of the Directed Hamiltonian Cycle Problem
• Towards Robust CNF Encodings of Cardinality Constraints
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• TSPLIB—A Traveling Salesman Problem Library
• Counterexample Guided Abstraction Refinement Algorithm for Propositional Circumscription
• Reducibility among Combinatorial Problems
• Computer Aided Verification
• Theory and Applications of Satisfiability Testing
• A Decision Procedure for Bit-Vectors and Arrays
• RESILIENT LKH: SECURE MULTICAST KEY DISTRIBUTION SCHEMES
• Boolean satisfiability with transitivity constraints

This page was built for publication: Incremental SAT-Based Method with Native Boolean Cardinality Handling for the Hamiltonian Cycle Problem