On the parameterized complexity of short computation and factorization
From MaRDI portal
Publication:1387097
DOI10.1007/s001530050069zbMath0944.68069OpenAlexW1982384331MaRDI QIDQ1387097
Michael R. Fellows, Rodney G. Downey, Li-Ming Cai, Jian'er Chen
Publication date: 2 June 1998
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s001530050069
completenessderivationsfactorizationsparameterized computational complexityhardness\(W\) hierarchynondeterministic machineparameterized computations of Turing machines
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Simplifying the weft hierarchy, Chordless paths through three vertices, On the parametric complexity of schedules to minimize tardy tasks., The Turing way to parameterized complexity, The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, A Parameterized Halting Problem, \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling], Sorting by prefix block-interchanges, Parameterized Complexity and Approximability of the SLCS Problem, Computation Models for Parameterized Complexity, Unnamed Item, Parameterized complexity and approximability of the longest compatible sequence problem, Confronting intractability via parameters, The complexity of irredundant sets parameterized by size, Fixed-parameter tractability and completeness II: On completeness for W[1], Advice classes of parametrized tractability, Reconfiguration on sparse graphs, Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy, W-hierarchies defined by symmetric gates, A parametric analysis of the state-explosion problem in model checking, Parameterized complexity of a coupled-task scheduling problem, On the parameterized complexity of multiple-interval graph problems, The complexity ecology of parameters: An illustration using bounded max leaf number, Threshold dominating sets and an improved characterization of \(W[2\)], On the space and circuit complexity of parameterized problems: classes and completeness, Synchronizing series-parallel deterministic finite automata with loops and related problems, Perfect Code is \(W[1\)-complete]
