On the structure of solution-graphs for Boolean formulas

DOI10.1007/978-3-319-22177-9_10MaRDI QIDQ2947874zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Solution-Graphs of Boolean Formulas and Isomorphism
• Solution-Graphs of Boolean Formulas and Isomorphism1
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits

Cites work

• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 1335887 (Why is no real title available?)
• scientific article; zbMATH DE number 1390075 (Why is no real title available?)
• A computational trichotomy for connectivity of Boolean satisfiability
• A new look at survey propagation and its generalizations
• A note on succinct representations of graphs
• Computational Complexity
• Equilateral sets in \(l_p^n\)
• Graphs and cubes
• Languages represented by Boolean formulas
• On connected Boolean functions
• Succinct Encodings of Graph Isomorphism
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The complexity of bounded length graph recoloring and CSP reconfiguration
• The complexity of satisfiability problems
• Two solutions to diluted p-spin models and XORSAT problems

Cited in

(10)

• On the Boolean Connectivity Problem for Horn Relations
• The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Solution-Graphs of Boolean Formulas and Isomorphism
• Complete Problems Involving Boolean Labelled Structures and Projection Transactions
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• On the capacity of Boolean graph formulæ
• Graph theoretic and Boolean conditions for structurally fixed modes of augmented system forms
• Solution-Graphs of Boolean Formulas and Isomorphism1
• Using extended resolution to represent strongly connected components of directed graphs

This page was built for publication: On the structure of solution-graphs for Boolean formulas

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