On the Structure of Solution-Graphs for Boolean Formulas

DOI10.1007/978-3-319-22177-9_10zbMath1436.94128OpenAlexW1572204789MaRDI QIDQ2947874

Patrick Scharpfenecker

Publication date: 29 September 2015

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-22177-9_10

zbMATH Keywords

embeddingconnectivitysatisfiabilitypartial cubesuccinct\(st\)-connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (94D10)

Related Items (3)

Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Solution-Graphs of Boolean Formulas and Isomorphism ⋮ Solution-Graphs of Boolean Formulas and Isomorphism1

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Languages represented by Boolean formulas
• Graphs and cubes
• Equilateral sets in \(l_p^n\)
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• On connected Boolean functions
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• A new look at survey propagation and its generalizations
• A note on succinct representations of graphs
• Computational Complexity
• The complexity of satisfiability problems
• Succinct Encodings of Graph Isomorphism
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: On the Structure of Solution-Graphs for Boolean Formulas