Complexity and Algorithms for Well-Structured k-SAT Instances

DOI10.1007/978-3-540-79719-7_10MaRDI QIDQ3502698zbMATH OpenOpenAlexFDO

Authors Konstantinos Georgiou, Periklis A. Papakonstantinou

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)

Recommendations

• Width-parametrized SAT: time-space tradeoffs
• Better algorithms for satisfiability problems for formulas of bounded rank-width
• On the diameter of the set of satisfying assignments in random satisfiable k-CNF formulas
• Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
• Counting truth assignments of formulas of bounded tree-width or clique-width

Cites work

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

Cited in

(8)

• 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
• NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT ≥ k ,r-UNLSAT ≥ k )
• On the K‐sat model with large number of clauses
• The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
• A note on width-parameterized SAT: an exact machine-model characterization

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

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