Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
From MaRDI portal
Publication:5361235
DOI10.1137/16M1065288zbMath1374.68247MaRDI QIDQ5361235
Venkatesh Raman, Naomi Nishimura, Amer E. Mouawad, Vinayak Pathak
Publication date: 27 September 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (9)
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Token sliding on graphs of girth five ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Token sliding on graphs of girth five ⋮ Optimal reconfiguration of optimal ladder lotteries ⋮ Dominating sets reconfiguration under token sliding ⋮ Homomorphism Reconfiguration via Homotopy ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ On reconfigurability of target sets
Cites Work
- 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
- Reconfiguration on sparse graphs
- Connectedness of the graph of vertex-colourings
- Transforming triangulations
- Rings of sets
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- The complexity of change
- Fixed-Parameter Tractability of Token Jumping on Planar Graphs
- Vertex Cover Reconfiguration and Beyond
- The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
- Finding Shortest Paths Between Graph Colourings
- Reconfiguration over Tree Decompositions
- γ-graphs of graphs
- Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
- Proximity-preserving labeling schemes
- Computational Complexity
- The complexity of satisfiability problems
- On the Parameterized Complexity for Token Jumping on Graphs
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
