dos Santos Souza, Uéverton; Protti, Fábio Tractability, hardness, and kernelization lower bound for and/or graph solution. (English) Zbl 1372.05224 Discrete Appl. Math. 232, 125-133 (2017). MSC: 05C99 68R10 68P05 68Q15 PDF BibTeX XML Cite \textit{U. dos Santos Souza} and \textit{F. Protti}, Discrete Appl. Math. 232, 125--133 (2017; Zbl 1372.05224) Full Text: DOI
Dell, Holger AND-compression of NP-complete problems: streamlined proof and minor observations. (English) Zbl 1350.68118 Algorithmica 75, No. 2, 403-423 (2016). MSC: 68Q17 05C65 68Q12 68Q25 94A17 PDF BibTeX XML Cite \textit{H. Dell}, Algorithmica 75, No. 2, 403--423 (2016; Zbl 1350.68118) Full Text: DOI
Drucker, Andrew New limits to classical and quantum instance compression. (English) Zbl 1330.68092 SIAM J. Comput. 44, No. 5, 1443-1479 (2015). MSC: 68Q17 68Q12 68Q15 68Q25 PDF BibTeX XML Cite \textit{A. Drucker}, SIAM J. Comput. 44, No. 5, 1443--1479 (2015; Zbl 1330.68092) Full Text: DOI
Hermelin, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi A completeness theory for polynomial (Turing) kernelization. (English) Zbl 1312.68102 Algorithmica 71, No. 3, 702-730 (2015). MSC: 68Q25 68Q15 68Q17 PDF BibTeX XML Cite \textit{D. Hermelin} et al., Algorithmica 71, No. 3, 702--730 (2015; Zbl 1312.68102) Full Text: DOI
Kratsch, Stefan Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. (English) Zbl 1398.68249 ACM Trans. Algorithms 10, No. 4, Article No. 19, 16 p. (2014). MSC: 68Q25 05C55 05C85 68Q17 PDF BibTeX XML Cite \textit{S. Kratsch}, ACM Trans. Algorithms 10, No. 4, Article No. 19, 16 p. (2014; Zbl 1398.68249) Full Text: DOI
Dell, Holger AND-compression of NP-complete problems: streamlined proof and minor observations. (English) Zbl 1341.68054 Cygan, Marek (ed.) et al., Parameterized and exact computation. 9th international symposium, IPEC 2014, Wroclaw, Poland, September 10–12, 2014. Revised selected papers. Cham: Springer (ISBN 978-3-319-13523-6/pbk; 978-3-319-13524-3/ebook). Lecture Notes in Computer Science 8894, 184-195 (2014). MSC: 68Q17 05C65 68Q12 68Q25 94A17 PDF BibTeX XML Cite \textit{H. Dell}, Lect. Notes Comput. Sci. 8894, 184--195 (2014; Zbl 1341.68054) Full Text: DOI
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan Kernelization lower bounds by cross-composition. (English) Zbl 1295.05222 SIAM J. Discrete Math. 28, No. 1, 277-305 (2014). MSC: 05C85 68Q17 68Q25 PDF BibTeX XML Cite \textit{H. L. Bodlaender} et al., SIAM J. Discrete Math. 28, No. 1, 277--305 (2014; Zbl 1295.05222) Full Text: DOI
Kratsch, Stefan; Wahlström, Magnus Two edge modification problems without polynomial kernels. (English) Zbl 06920189 Discrete Optim. 10, No. 3, 193-199 (2013). MSC: 90C PDF BibTeX XML Cite \textit{S. Kratsch} and \textit{M. Wahlström}, Discrete Optim. 10, No. 3, 193--199 (2013; Zbl 06920189) Full Text: DOI
Hermelin, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi A completeness theory for polynomial (Turing) kernelization. (English) Zbl 1407.68224 Gutin, Gregory (ed.) et al., Parameterized and exact computation. 8th international symposium, IPEC 2013, Sophia Antipolis, France, September 4–6, 2013. Revised selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 8246, 202-215 (2013). MSC: 68Q25 68Q15 68Q17 PDF BibTeX XML Cite \textit{D. Hermelin} et al., Lect. Notes Comput. Sci. 8246, 202--215 (2013; Zbl 1407.68224) Full Text: DOI
Kratsch, Stefan Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. (English) Zbl 1423.68216 Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 114-122 (2012). MSC: 68Q25 05C55 05C85 68Q17 PDF BibTeX XML Cite \textit{S. Kratsch}, in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 114--122 (2012; Zbl 1423.68216) Full Text: Link
Chakraborty, Chiranjit; Santhanam, Rahul Instance compression for the polynomial hierarchy and beyond. (English) Zbl 1375.68057 Thilikos, Dimitrios M. (ed.) et al., Parameterized and exact computation. 7th international symposium, IPEC 2012, Ljubljana, Slovenia, September 12–14, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-33292-0/pbk). Lecture Notes in Computer Science 7535, 120-134 (2012). MSC: 68Q15 68Q17 68Q25 PDF BibTeX XML Cite \textit{C. Chakraborty} and \textit{R. Santhanam}, Lect. Notes Comput. Sci. 7535, 120--134 (2012; Zbl 1375.68057) Full Text: DOI
Bodlaender, Hans L.; Thomassé, Stéphan; Yeo, Anders Kernel bounds for disjoint cycles and disjoint paths. (English) Zbl 1221.68099 Theor. Comput. Sci. 412, No. 35, 4570-4578 (2011). MSC: 68Q25 68Q17 PDF BibTeX XML Cite \textit{H. L. Bodlaender} et al., Theor. Comput. Sci. 412, No. 35, 4570--4578 (2011; Zbl 1221.68099) Full Text: DOI