Publication:4281497
From MaRDI portal
zbMath0799.68087MaRDI QIDQ4281497
Michael R. Fellows, Rodney G. Downey
Publication date: 13 November 1994
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, On the Complexity of Singly Connected Vertex Deletion, On the Parameterized Complexity of the Expected Coverage Problem, A Retrospective on (Meta) Kernelization, Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues, Exploring the Kernelization Borders for Hitting Cycles, An improved FPT algorithm for independent feedback vertex set, The Parameterized Complexity of Graph Cyclability, Domino treewidth, Improved FPT Algorithms for Deletion to Forest-Like Structures., On group feedback vertex set parameterized by the size of the cutset, Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms, Confronting intractability via parameters, Graphs with few \(P_4\)'s under the convexity of paths of order three, On feedback vertex set: new measure and new structures, Dominating set is fixed parameter tractable in claw-free graphs, Fixed-parameter tractability and completeness II: On completeness for W[1], Advice classes of parametrized tractability, On parameterized independent feedback vertex set, Compactors for parameterized counting problems, Parameterized power domination complexity, On the hardness of labeled correlation clustering problem: a parameterized complexity view, Efficient algorithms for counting parameterized list \(H\)-colorings, Improved algorithms for feedback vertex set problems, Parameterized circuit complexity and the \(W\) hierarchy, The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling], Improved analysis of highest-degree branching for feedback vertex set, On the parameterized complexity of the expected coverage problem, From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability, Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers, A polynomial kernel for block graph deletion, Sparse parameterized problems, Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits, The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, A Parameterized Halting Problem, Reachability in Graph Transformation Systems and Slice Languages, Subset Feedback Vertex Set Is Fixed-Parameter Tractable, A Quartic Kernel for Pathwidth-One Vertex Deletion