Strong computational lower bounds via parameterized complexity
Authors:
- Jianer ChenJCJianer Chen
- Xiuzhen HuangXHXiuzhen Huang
- Iyad A. KanjIKIyad A. Kanj
- Ge XiaGXGe Xia
- 1 December 2006
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 72 (8) , 1346-1367
Abstract
No abstract availableKeywords
This publication has 22 references indexed in Scilit:
- Solving large FPT problems on coarse-grained parallel machinesJournal of Computer and System Sciences, 2003
- Cutting Up Is Hard To DoElectronic Notes in Theoretical Computer Science, 2003
- Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar GraphsAlgorithmica, 2002
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- Vertex Cover: Further Observations and Further ImprovementsJournal of Algorithms, 2001
- On the Complexity of Database QueriesJournal of Computer and System Sciences, 1999
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Matrix multiplication via arithmetic progressionsJournal of Symbolic Computation, 1990
- Algorithms for maximum independent setsJournal of Algorithms, 1986
- An O(20.304n) Algorithm for Solving Maximum Independent Set ProblemIEEE Transactions on Computers, 1986