On the Space Complexity of Parameterized Problems

DOI10.1007/978-3-642-33293-7_20MaRDI QIDQ4899254zbMATH OpenOpenAlexFDO

Authors Michael Elberfeld, Christoph Stockhusen, Till Tantau

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-33293-7_20

zbMATH Keywords

feedback vertex setfixed-parameter tractable problemslogarithmic spaceparameterized complexity theoryreachability problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the space and circuit complexity of parameterized problems: classes and completeness
• scientific article; zbMATH DE number 1161563
• On space-efficient algorithms for certain NP-complete problems
• On Parameterized Approximability
• Parameterized and Exact Computation
• Parameterized complexity of constraint satisfaction problems
• Fundamentals of parameterized complexity
• On the structure of parameterized problems in NP
• The Parameterized Complexity of Maximality and Minimality Problems

Cited in

(5)

• On the space and circuit complexity of parameterized problems: classes and completeness
• Completeness results for parameterized space classes
• A Note on the Space Complexity of Fast D-Finite Function Evaluation
• On the parameterized complexity of non-monotonic logics
• Parameterized Complexity of DPLL Search Procedures

This page was built for publication: On the Space Complexity of Parameterized Problems

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