Community Structure Inspired Algorithms for SAT and #SAT

DOI10.1007/978-3-319-24318-4_17zbMath1471.68322OpenAlexW2157837456MaRDI QIDQ3453228

Stefan Szeider, Robert Ganian

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Related Items

New width parameters for SAT and \#SAT ⋮ The complexity landscape of decompositional parameters for ILP ⋮ On the Hardness of SAT with Community Structure

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Treewidth. Computations and approximations
• On the structure of some classes of minimal unsatisfiable formulas
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• On simple characterizations of k-trees
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• Algorithms for propositional model counting
• Solving \#SAT using vertex covers
• Impact of Community Structure on SAT Solver Performance
• The Fractal Dimension of SAT Formulas
• Graph minors. II. Algorithmic aspects of tree-width
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• The Structure and Function of Complex Networks
• Community structure in social and biological networks
• The Complexity of Valued Constraint Satisfaction Problems
• Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
• Theory and Applications of Satisfiability Testing
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: Community Structure Inspired Algorithms for SAT and #SAT