The Turing way to parameterized complexity
type: Item
instance of: scholarly article
title: The Turing way to parameterized complexity
zbMATH Open document ID: 1114.68045
DOI: 10.1016/S0022-0000(03)00073-4
author: Marco Cesati
published in: Journal of Computer and System Sciences
publication date: 2004-08-19T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 2092866
zbMATH Keywords: Parameterized complexity
zbMATH Keywords: W-class membership
zbMATH Keywords: Turing machine
zbMATH Keywords: Halting problem
MaRDI profile type: Publication
cites work: Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
cites work: On intervalizing \(k\)-colored graphs for DNA physical mapping
cites work: On the parameterized complexity of short computation and factorization
cites work: Perfect Code is \(W[1]\)-complete
cites work: Computation Models for Parameterized Complexity
cites work: Fixed-parameter tractability and completeness II: On completeness for W[1]
cites work: Fixed-Parameter Tractability and Completeness I: Basic Results
cites work: Threshold dominating sets and an improved characterization of \(W[2]\)
cites work: Q4503944
cites work: Q4501141
cites work: The steiner problem in graphs
cites work: Q4544433
Recommended article: A Parameterized Complexity Tutorial
Recommended article: Parameterized complexity: the main ideas and connections to practical computing
Recommended article: Q4417671
Recommended article: Q4393480
Recommended article: Fundamentals of parameterized complexity
Recommended article: The Birth and Early Years of Parameterized Complexity
Recommended article: Parameterized computation and complexity: a new approach dealing with NP-hardness
Recommended article: Parameterized Complexity and Subexponential-Time Computability
Recommended article: Parameterized proof complexity
Recommended article: Computation Models for Parameterized Complexity
description: scientific article; zbMATH DE number 2092866