Kernelization lower bounds for finding constant-size subgraphs

DOI10.1007/978-3-319-94418-0_19MaRDI QIDQ1670739zbMATH OpenOpenAlexFDO

Authors Till Fluschnik, George B. Mertzios, André Nichterlein

Publication date 6 September 2018

Full work available at URL https://arxiv.org/abs/1710.07601, http://dro.dur.ac.uk/26175/1/26175.pdf

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Kernelization: new upper and lower bound techniques
• On problems without polynomial kernels
• Lower bounds for kernelization
• Lower bounds on kernelization
• On Problems without Polynomial Kernels (Extended Abstract)

Cited in

(1)

• Maximum matching in almost linear time on graphs of bounded clique-width

This page was built for publication: Kernelization lower bounds for finding constant-size subgraphs

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