Hamiltonian cycle reconfiguration with answer set programming

DOI10.1007/978-3-031-43619-2_19MaRDI QIDQ6545539zbMATH OpenFDO

Authors Takahiro Hirate, Mutsunori Banbara, Katsumi Inoue, Xiao-Nan Lu, Hidetomo Nabeshima, Torsten Schaub, Takehide Soh, Naoyuki Tamura

Publication date 29 May 2024

Full work available at URL https://doi.org/10.1007/978-3-031-43619-2_19

zbMATH Keywords

answer set programmingcombinatorial reconfigurationHamiltonian cycle reconfiguration

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27)

Recommendations

• Complexity of Hamiltonian cycle reconfiguration
• Recongo: bounded combinatorial reconfiguration with answer set programming
• Incremental SAT-based method with native Boolean cardinality handling for the Hamiltonian cycle problem
• Introduction to reconfiguration
• On the Complexity of Reconfiguration Problems

Cites work

• A dichotomy theorem for circular colouring reconfiguration
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Answer set programming
• Answer set programming modulo acyclicity
• Chinese remainder encoding for Hamiltonian cycles
• Complexity of Hamiltonian cycle reconfiguration
• Complexity of independent set reconfigurability problems
• FHCP challenge set: the first set of structurally difficult instances of the Hamiltonian cycle problem
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Incremental SAT-based method with native Boolean cardinality handling for the Hamiltonian cycle problem
• Introduction to reconfiguration
• Knowledge Representation, Reasoning and Declarative Problem Solving
• Logic programs with stable model semantics as a constraint programming paradigm
• On the complexity of reconfiguration problems
• On the Parameterized Complexity for Token Jumping on Graphs
• Reconfiguration of cliques in a graph
• Reconfiguration of list edge-colorings in a graph
• Reducibility among combinatorial problems
• Shortest reconfiguration paths in the solution space of Boolean formulas
• The complexity of change
• The complexity of dominating set reconfiguration
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Cited in

(3)

• Recongo: bounded combinatorial reconfiguration with answer set programming
• Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
• Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs

This page was built for publication: Hamiltonian cycle reconfiguration with answer set programming

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