Sparse parameterized problems

DOI10.1016/0168-0072(95)00069-0MaRDI QIDQ2564046zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Marco Cesati, Michael R. Fellows

Publication date 13 February 1997

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(95)00069-0

zbMATH Keywords

complexity theory for parametrized problemsMahaney's theorem for sparse sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Parametrized complexity theory.
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Parameterized complexity of sparse linear complementarity problems
• Parameterized complexity of sparse linear complementarity problems
• scientific article; zbMATH DE number 806748

Cites work

• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• scientific article; zbMATH DE number 512804 (Why is no real title available?)
• scientific article; zbMATH DE number 512844 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis

Cited in

(6)

• Finding sparse systems of parameters
• Parameterized circuit complexity and the \(W\) hierarchy
• Confronting intractability via parameters
• Parameterized complexity of sparse linear complementarity problems
• Parameterized complexity of sparse linear complementarity problems
• Vertex cover, dominating set and my encounters with parameterized complexity and Mike Fellows

This page was built for publication: Sparse parameterized problems

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