Solution-Graphs of Boolean Formulas and Isomorphism
DOI10.1007/978-3-319-40970-2_3zbMath1475.68223OpenAlexW2488409468MaRDI QIDQ2817999
Patrick Scharpfenecker, Jacobo Toran
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational aspects of satisfiability (68R07)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Completeness results for graph 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
This page was built for publication: Solution-Graphs of Boolean Formulas and Isomorphism
