Strong computational lower bounds via parameterized complexity

2006/05/25 by Jianer Chen, Xiuzhen Huang, Iyad Kanj +2 · 7 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems

paper · doi:10.1016/j.jcss.2006.04.007

openalex publication_date 2006/05/25 · crossref created 2006/05/25 · crossref issued 2006/12/01 · crossref published 2006/12/01 · crossref published-print 2006/12/01 · crossref deposited 2019/01/16 · openalex created_date 2025/10/10 · crossref indexed 2026/07/17 · openalex updated_date 2026/07/23

Citations

• Which Problems Have Strongly Exponential Complexity?

Cited by

• Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
• On the independent set problem in random graphs
• Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
• On the Tractability Landscape of the Conditional Minisum Approval Voting Rule
• 2-satisfiability [wikipedia]
• Clique problem [wikipedia]
• Logic of graphs [wikipedia]