Complexity and Algorithms for Well-Structured k-SAT Instances
From MaRDI portal
Publication:3502698
DOI10.1007/978-3-540-79719-7_10zbMath1138.68538MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
A note on width-parameterized SAT: an exact machine-model characterization, Size-treewidth tradeoffs for circuits computing the element distinctness function, On the satisfiability of quantum circuits of small treewidth, Satisfiability with index dependency, On the Satisfiability of Quantum Circuits of Small Treewidth
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