From the W-hierarchy to XNLP. Classes of fixed parameter intractability

DOI10.1007/978-3-030-96731-4_2MaRDI QIDQ2154075zbMATH OpenOpenAlexFDO

Authors Hans L. Bodlaender

Publication date 13 July 2022

Full work available at URL https://doi.org/10.1007/978-3-030-96731-4_2

zbMATH Keywords

\(W\)-hierarchyparameterized complexityXNLPXP

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Classes of Pebble Games and Complete Problems
• Collaborating with Hans: Some Remaining Wonderments
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 512804 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Kernelization. Theory of parameterized preprocessing
• Nonconstructive advances in polynomial-time complexity
• Nonconstructive tools for proving polynomial-time decidability
• On problems without polynomial kernels
• On space efficiency of algorithms working on structural decompositions of graphs
• On the space and circuit complexity of parameterized problems: classes and completeness
• Parameterized algorithms
• Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
• Parameterized complexity of bandwidth on trees
• Parametrized complexity theory.
• Some combinatorial game problems require Ω( n ^k ) time
• Strong computational lower bounds via parameterized complexity
• The complexity of theorem-proving procedures
• The disjoint paths problem in quadratic time
• The Parameterized Complexity of Counting Problems
• Undirected connectivity in log-space

This page was built for publication: From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability

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