Solution-Graphs of Boolean Formulas and Isomorphism

DOI10.1007/978-3-319-40970-2_3MaRDI QIDQ2817999zbMATH OpenOpenAlexFDO

Authors Patrick Scharpfenecker, Jacobo Torán

Publication date 5 September 2016

Published in Theory and Applications of Satisfiability Testing – SAT 2016 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-40970-2_3

zbMATH Keywords

countingisomorphismpartial cubesolution graph

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational aspects of satisfiability (68R07)

Recommendations

• Solution-Graphs of Boolean Formulas and Isomorphism1
• On the structure of solution-graphs for Boolean formulas
• scientific article; zbMATH DE number 1948177
• Hypergraph isomorphism and structural equivalence of Boolean functions
• Proof graphs for parameterised Boolean equation systems
• Analysis of Boolean equation systems through structure graphs
• scientific article; zbMATH DE number 3952822
• Polynomial equivalence of the problems ``predicate formulas isomorphism and graph isomorphism

Cites work

• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 1948177 (Why is no real title available?)
• A computational trichotomy for connectivity of Boolean satisfiability
• Completeness results for graph isomorphism.
• Embedding Topological Median Algebras in Products of Dendrons
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph isomorphism is low for PP
• Graphs and cubes
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Metric graph theory and geometry: a survey
• On the interpolation between product-based message passing heuristics for SAT
• On the power of deterministic reductions to C=P
• On the solution-space geometry of random constraint satisfaction problems
• On the structure of solution-graphs for Boolean formulas
• Parity separation: a scientifically proven method for permanent weight loss
• The Complexity of Enumeration and Reliability Problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The complexity of combinatorial problems with succinct input representation
• The complexity of computing the permanent
• The complexity of satisfiability problems

Cited in

(4)

• On the structure of solution-graphs for Boolean formulas
• On the Boolean connectivity problem for Horn relations
• scientific article; zbMATH DE number 1948177 (Why is no real title available?)
• Solution-Graphs of Boolean Formulas and Isomorphism1

This page was built for publication: Solution-Graphs of Boolean Formulas and Isomorphism

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