Complexity and Algorithms for Well-Structured k-SAT Instances

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

Mathematics Subject Classification ID

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, Satisfiability with index dependency

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