Solution-Graphs of Boolean Formulas and Isomorphism1

DOI10.3233/SAT190113zbMath1484.68146OpenAlexW2991434245MaRDI QIDQ5015600

Patrick Scharpfenecker, Jacobo Toran

Publication date: 9 December 2021

Published in: Journal on Satisfiability, Boolean Modeling and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/sat190113

zbMATH Keywords

countingisomorphismpartial cubesolution-graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational aspects of satisfiability (68R07)

Cites Work

• The complexity of computing the permanent
• Graphs and cubes
• The complexity of combinatorial problems with succinct input representation
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Graph isomorphism is low for PP
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Completeness results for graph isomorphism.
• Solution-Graphs of Boolean Formulas and Isomorphism
• On the Structure of Solution-Graphs for Boolean Formulas
• The Complexity of Enumeration and Reliability Problems
• On the power of deterministic reductions to C=P
• Parity Separation: A Scientifically Proven Method for Permanent Weight Loss
• Embedding Topological Median Algebras in Products of Dendrons
• On the Interpolation between Product-Based Message Passing Heuristics for SAT
• Graph isomorphism in quasipolynomial time [extended abstract]
• The complexity of satisfiability problems
• On the solution‐space geometry of random constraint satisfaction problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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