The Turing way to parameterized complexity
From MaRDI portal
Publication:1877697
DOI10.1016/S0022-0000(03)00073-4zbMath1114.68045MaRDI QIDQ1877697
Publication date: 19 August 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (33)
Chordless paths through three vertices ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ On the parameterised complexity of string morphism problems ⋮ A Parameterized Halting Problem ⋮ On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]] ⋮ The complexity of probabilistic lobbying ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ On the complexity of various parameterizations of common induced subgraph isomorphism ⋮ Finding approximate and constrained motifs in graphs ⋮ Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems ⋮ Facility Location Problems: A Parameterized View ⋮ Dual parameterization and parameterized approximability of subset graph problems ⋮ The many facets of upper domination ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ Parameterized proof complexity ⋮ Confronting intractability via parameters ⋮ Parameterized Dynamic Variants of Red-Blue Dominating Set ⋮ Finding Approximate and Constrained Motifs in Graphs ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ R<scp>OMAN DOMINATION</scp>: a parameterized perspective† ⋮ Facility location problems: a parameterized view ⋮ Parameterized certificate dispersal and its variants ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective ⋮ Unnamed Item ⋮ The complexity of finding harmless individuals in social networks ⋮ Parameterized counting problems ⋮ Unnamed Item ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ Parameterizations of hitting set of bundles and inverse scope ⋮ Perfect Code is \(W[1\)-complete] ⋮ A complete parameterized complexity analysis of bounded planning
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Threshold dominating sets and an improved characterization of \(W[2\)]
- On the parameterized complexity of short computation and factorization
- Perfect Code is \(W[1\)-complete]
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Computation Models for Parameterized Complexity
- Fixed-Parameter Tractability and Completeness I: Basic Results
- The steiner problem in graphs
- On intervalizing \(k\)-colored graphs for DNA physical mapping
This page was built for publication: The Turing way to parameterized complexity
