Computation Models for Parameterized Complexity

DOI10.1002/MALQ.19970430204MaRDI QIDQ4336699zbMATH OpenOpenAlexFDO

Authors Marco Cesati, Miriam Di Ianni

Publication date 14 May 1997

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2108/260205

zbMATH Keywords

parameterized computational problemTuring machines

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1161563
• Complexity models for incremental computation
• Fundamentals of parameterized complexity
• Parameterized complexity: the main ideas and connections to practical computing
• scientific article; zbMATH DE number 1956210
• Parameterized Complexity and Logic
• Modified parameterized complexity theory
• scientific article; zbMATH DE number 1424025
• Parametrized complexity theory.

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the parameterized complexity of short computation and factorization

Cited in

(27)

• On problems without polynomial kernels
• Polynomial-time versus recursive models
• On the parameterized complexity of short computation and factorization
• Perfect Code is \(W[1]\)-complete
• The Turing way to parameterized complexity
• A multi-parameter analysis of hard problems on deterministic finite automata
• On the space and circuit complexity of parameterized problems: classes and completeness
• On the computational complexity of cost efficiency analysis models
• A parametric analysis of the state-explosion problem in model checking
• On the structure of parameterized problems in NP
• Computational complexity in non-Turing models of computation: the what, the why and the how
• Parameterized complexity: the main ideas and connections to practical computing
• On the efficiency of polynomial time approximation schemes
• A Parameterized Halting Problem
• Fixed-parameter decidability: extending parameterized complexity analysis
• Fixed Structure Complexity
• Complexity of Ehrenfeucht models
• A logic for PTIME and a parameterized halting problem
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 2183396 (Why is no real title available?)
• Relativization and interactive proof systems in parameterized complexity theory
• A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
• Machine characterizations for parameterized complexity classes beyond para-NP
• R<scp>OMAN DOMINATION</scp>: a parameterized perspective†
• Modified parameterized complexity theory
• Machine-based methods in parameterized complexity theory
• Computing the complexity for Schelling segregation models

This page was built for publication: Computation Models for Parameterized Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4336699)