On parameterized exponential time complexity
type: Item
instance of: scholarly article
title: On parameterized exponential time complexity
zbMATH Open document ID: 1172.68023
author: Iyad Kanj
author: Ge Xia
author: Jianer Chen
published in: Theoretical Computer Science
publication date: 2009-07-10T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5577374
zbMATH Keywords: parameterized complexity
zbMATH Keywords: subexponential time complexity
zbMATH Keywords: parameterized algorithms
zbMATH Keywords: exact algorithms
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.03.006
OpenAlex ID: W2157494948
cites work: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
cites work: An improved fixed-parameter algorithm for vertex cover
cites work: Q3221758
cites work: Nondeterminism within $P^ * $
cites work: On the existence of subexponential parameterized algorithms
cites work: Refined memorization for vertex cover
cites work: Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
cites work: Strong computational lower bounds via parameterized complexity
cites work: On the computational hardness based on linear fpt-reductions
cites work: Vertex cover: Further observations and further improvements
cites work: Improved Parameterized Upper Bounds for Vertex Cover
cites work: Tight lower bounds for certain parameterized NP-hard problems
cites work: Q4715442
cites work: Q4263467
cites work: Q4393480
cites work: Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
cites work: Q4198056
cites work: Which problems have strongly exponential complexity?
cites work: Q4252414
cites work: Q4708588
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: Vertex packings: Structural properties and algorithms
cites work: Q4251072
cites work: On efficient fixed-parameter algorithms for weighted vertex cover
DOI: 10.1016/J.TCS.2009.03.006
description: scientific article; zbMATH DE number 5577374