Strong computational lower bounds via parameterized complexity
type: Item
instance of: scholarly article
title: Strong computational lower bounds via parameterized complexity
zbMATH Open document ID: 1119.68092
author: Xiuzhen Huang
author: Iyad Kanj
author: Ge Xia
author: Jianer Chen
published in: Journal of Computer and System Sciences
publication date: 2006-12-07T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5078609
zbMATH Keywords: parameterized computation
zbMATH Keywords: computational complexity
zbMATH Keywords: lower bound
zbMATH Keywords: clique
zbMATH Keywords: polynomial time approximation scheme
MaRDI profile type: Publication
full work available at URL: j.jcss.2006.04.007
OpenAlex ID: W2130190334
Wikidata QID: Q55891718
cites work: Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
cites work: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
cites work: Q4258216
cites work: Q4252376
cites work: Solving large FPT problems on coarse-grained parallel machines
cites work: Characterizing parallel hierarchies by reducibilities
cites work: Vertex cover: Further observations and further improvements
cites work: Tight lower bounds for certain parameterized NP-hard problems
cites work: Matrix multiplication via arithmetic progressions
cites work: Q4737204
cites work: Genetic Design of Drugs Without Side-Effects
cites work: Q4393480
cites work: Q4259986
cites work: Fundamentals of Computation Theory
cites work: Which problems have strongly exponential complexity?
cites work: An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
cites work: Vertex packings: Structural properties and algorithms
cites work: Q3688439
cites work: Q4251072
cites work: Optimization, approximation, and complexity classes
cites work: On limited nondeterminism and the complexity of the V-C dimension
cites work: On the complexity of database queries
cites work: Algorithms for maximum independent sets
cites work: Finding a Maximum Independent Set
DOI: 10.1016/J.JCSS.2006.04.007
description: scientific article; zbMATH DE number 5078609