Complexity and Algorithms for Well-Structured k-SAT Instances

DOI10.1007/978-3-540-79719-7_10zbMath1138.68538OpenAlexW1558213091MaRDI QIDQ3502698

Periklis A. Papakonstantinou, Konstantinos Georgiou

Publication date: 27 May 2008

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

Full work available at URL: https://doi.org/10.1007/978-3-540-79719-7_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (5)

Satisfiability with index dependency ⋮ On the Satisfiability of Quantum Circuits of Small Treewidth ⋮ On the satisfiability of quantum circuits of small treewidth ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ A note on width-parameterized SAT: an exact machine-model characterization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Satisfiability, branch-width and Tseitin tautologies
• The complexity of computing the permanent
• Graph minors. I. Excluding a forest
• On uniform circuit complexity
• The NP-completeness of the bandwidth minimization problem
• Approximating the bandwidth via volume respecting embeddings
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Bandwidth of the complete \(k\)-ary tree
• On powers of graphs of bounded NLC-width (clique-width)
• Approximating clique-width and branch-width
• Fast Parallel Computation of Polynomials Using Few Processors
• Algorithms for Propositional Model Counting
• Constraint Satisfaction with Bounded Treewidth Revisited
• Graph minors. II. Algorithmic aspects of tree-width
• Probabilistic checking of proofs
• Applications of a Planar Separator Theorem
• The bandwidth problem for graphs and matrices—a survey
• On the Tape Complexity of Deterministic Context-Free Languages
• Complexity Results for Bandwidth Minimization
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Theory and Applications of Satisfiability Testing
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• The complexity of theorem-proving procedures
• Solving #SAT Using Vertex Covers
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: Complexity and Algorithms for Well-Structured k-SAT Instances