Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability
type: Item
instance of: scholarly article
title: Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability
zbMATH Open document ID: 1194.68208
author: Yong Gao
published in: Artificial Intelligence
publication date: 2009-09-14T00:00:00Z
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5603694
zbMATH Keywords: weighted CNF satisfiability
zbMATH Keywords: fixed parameter tractability
zbMATH Keywords: data reduction
zbMATH Keywords: random instances
zbMATH Keywords: phase transitions
zbMATH Keywords: probabilistic analysis
zbMATH Keywords: resolution complexity
describes a project that uses: BG-WalkSAT
MaRDI profile type: Publication
full work available at URL: j.artint.2009.06.005
OpenAlex ID: W2105786826
cites work: Q5715725
cites work: The threshold for random k-SAT is 2 k (ln 2 - O(k))
cites work: On the solution-space geometry of random constraint satisfaction problems
cites work: Experiments on data reduction for optimal domination in networks
cites work: A Spectral Technique for Coloring Random 3-Colorable Graphs
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: The efficiency of resolution and Davis-Putnam procedures
cites work: Q4488089
cites work: Short proofs are narrow—resolution made simple
cites work: Exact Algorithms for Cluster Editing: Evaluation and Experiments
cites work: Paths in graphs
cites work: The scaling window of the 2-SAT transition
cites work: Q4012216
cites work: Coloring bipartite hypergraphs
cites work: Tight lower bounds for certain parameterized NP-hard problems
cites work: Q2934608
cites work: Q3576756
cites work: Q4375756
cites work: Q3624065
cites work: Frozen development in graph coloring
cites work: Tradeoffs in the Complexity of Backdoor Detection
cites work: Q4503944
cites work: Faster fixed-parameter tractable algorithms for matching and packing problems
cites work: Q4471318
cites work: Q3396567
cites work: Q4411142
cites work: Q3624064
cites work: Statistical regimes across constrainedness regions
cites work: Q3184605
cites work: Fixed-parameter complexity in AI and nonmonotonic reasoning
cites work: Data Reduction, Exact, and Heuristic Algorithms for Clique Cover
cites work: Q3624048
cites work: Solving random satisfiable 3CNF formulas in expected polynomial time
cites work: Parameterized complexity of constraint satisfaction problems
cites work: General percolation and random graphs
cites work: Models and thresholds for random constraint satisfaction problems
cites work: Q5710169
cites work: Backdoor sets for DLL subsolvers
cites work: Q4230728
cites work: Random constraint satisfaction: easy generation of hard (satisfiable) instances
DOI: 10.1016/J.ARTINT.2009.06.005
description: scientific article; zbMATH DE number 5603694