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

DOI10.1007/978-3-030-96731-4_2OpenAlexW4226134022MaRDI QIDQ2154075

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

parameterized complexityXP\(W\)-hierarchyXNLP

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• The disjoint paths problem in quadratic time
• On the parameterized complexity of reconfiguration problems
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Strong computational lower bounds via parameterized complexity
• On problems without polynomial kernels
• Nonconstructive advances in polynomial-time complexity
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• On the space and circuit complexity of parameterized problems: classes and completeness
• Parametrized complexity theory.
• Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
• Beyond NP-completeness for problems of bounded width (extended abstract)
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Undirected connectivity in log-space
• Some combinatorial game problems require Ω( n ^k ) time
• Nonconstructive tools for proving polynomial-time decidability
• Classes of Pebble Games and Complete Problems
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Kernelization
• The Parameterized Complexity of Counting Problems
• Fixed-Parameter Tractability and Completeness I: Basic Results
• On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
• Collaborating with Hans: Some Remaining Wonderments
• Parameterized Complexity of Bandwidth on Trees
• Parameterized Algorithms
• The complexity of theorem-proving procedures

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