Parameterized problems complete for nondeterministic FPT time and logarithmic space

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Fundamentals of parameterized complexity
On the complexity of some colorful problems parameterized by treewidth
Fixed-parameter tractability and completeness II: On completeness for W[1]
The complexity of finding uniform emulations on paths and ring networks
On the parameterized complexity of multiple-interval graph problems
Linear time algorithms for NP-hard problems restricted to partial k- trees
The NP-completeness of the bandwidth minimization problem
The polynomial-time hierarchy
Generalized coloring for tree-like graphs
The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
\(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
Treewidth, kernels, and algorithms. Essays dedicated to Hans L. Bodlaender on the occasion of his 60th birthday
On the space and circuit complexity of parameterized problems: classes and completeness
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
Losing Weight by Gaining Edges
The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
Quotient Networks
Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
Algorithms for Vertex Partitioning Problems on Partial k-Trees
Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
The Pathwidth and Treewidth of Cographs
Fixed-Parameter Tractability and Completeness I: Basic Results
Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
Parameterized Complexity of Bandwidth on Trees
Parameterized Algorithms
Upward and orthogonal planarity are W[1-hard parameterized by treewidth]

This page was built for publication: Parameterized problems complete for nondeterministic FPT time and logarithmic space

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