Random Instances of W[2]-Complete Problems: Thresholds, Complexity, and Algorithms

DOI10.1007/978-3-540-79719-7_9zbMath1138.68425OpenAlexW1522076887MaRDI QIDQ3502697

Yong Gao

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_9

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Threshold dominating cliques in random graphs and interval routing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Statistical regimes across constrainedness regions
• Backdoor sets for DLL subsolvers
• An exact algorithm for the minimum dominating clique problem
• The Efficiency of Resolution and Davis--Putnam Procedures
• Tradeoffs in the Complexity of Backdoor Detection
• A sharp threshold in proof complexity
• A machine program for theorem-proving

This page was built for publication: Random Instances of W[2]-Complete Problems: Thresholds, Complexity, and Algorithms