Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas

DOI10.1007/978-3-662-47672-7_80zbMath1374.68246arXiv1404.3801OpenAlexW1579633601MaRDI QIDQ3448854

Naomi Nishimura, Vinayak Pathak, Amer E. Mouawad, Venkatesh Raman

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1404.3801

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (16)

On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Ground State Connectivity of Local Hamiltonians ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Reconfiguration on nowhere dense graph classes ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Rerouting shortest paths in planar graphs ⋮ The connectivity of Boolean satisfiability: dichotomies for formulas and circuits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ The complexity of dominating set reconfiguration ⋮ On the parameterized complexity of reconfiguration problems ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Shortest Reconfiguration of Sliding Tokens on a Caterpillar ⋮ Reconfiguration of Steiner Trees in an Unweighted Graph ⋮ Introduction to reconfiguration

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of independent set reconfigurability problems
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• Reconfiguration of list edge-colorings in a graph
• Flip distance between triangulations of a simple polygon is NP-complete
• A note on some tree similarity measures
• Recoloring graphs via tree decompositions
• Connectedness of the graph of vertex-colourings
• Transforming triangulations
• Rings of sets
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Vertex Cover Reconfiguration and Beyond
• γ-graphs of graphs
• Computational Complexity
• The complexity of satisfiability problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas