Community structure inspired algorithms for SAT and \#SAT

DOI10.1007/978-3-319-24318-4_17zbMATH Open1471.68322OpenAlexW2157837456MaRDI QIDQ3453228FDOQ3453228

Authors: Robert Ganian, Stefan Szeider 

Publication date: 20 November 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-24318-4_17

Recommendations

• New width parameters for SAT and \#SAT
• The community structure of SAT formulas
• Community structure in industrial SAT instances
• On the hardness of SAT with community structure
• Model counting for CNF formulas of bounded modular treewidth

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) Nonnumerical algorithms (68W05) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Cites Work

• Graph theory
• The Structure and Function of Complex Networks
• Community structure in social and biological networks
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithms for propositional model counting
• Title not available (Why is that?)
• Graph minors. II. Algorithmic aspects of tree-width
• The complexity of valued constraint satisfaction problems
• Treewidth. Computations and approximations
• On simple characterizations of k-trees
• Theory and Applications of Satisfiability Testing
• Impact of Community Structure on SAT Solver Performance
• The fractal dimension of SAT formulas
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Solving \#SAT and Bayesian inference with backtracking search
• Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
• On the structure of some classes of minimal unsatisfiable formulas
• Solving \#SAT using vertex covers
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• Satisfiable formulas closed under replacement

Cited In (7)

• Impact of Community Structure on SAT Solver Performance
• Backdoor DNFs
• The complexity landscape of decompositional parameters for ILP
• New width parameters for SAT and \#SAT
• Generating SAT instances with community structure
• Community-Based Partitioning for MaxSAT Solving
• On the hardness of SAT with community structure

Uses Software

• JBool

This page was built for publication: Community structure inspired algorithms for SAT and \#SAT

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