GAJARSKÝ, Jakub, Petr HLINĚNÝ, Jan OBDRŽÁLEK, Sebastian ORDYNIAK, Felix REIDL, Peter ROSSMANITH, Fernando VILLAAMIL a Somnath SIKDAR. Kernelization using structural parameters on sparse graph classes. Journal of Computer and System Sciences. SAN DIEGO: Elsevier, 2017, roč. 84, č. 1, s. 219-242. ISSN 0022-0000. Dostupné z: https://dx.doi.org/10.1016/j.jcss.2016.09.002. |
Další formáty:
BibTeX
LaTeX
RIS
@article{1372352, author = {Gajarský, Jakub and Hliněný, Petr and Obdržálek, Jan and Ordyniak, Sebastian and Reidl, Felix and Rossmanith, Peter and Villaamil, Fernando and Sikdar, Somnath}, article_location = {SAN DIEGO}, article_number = {1}, doi = {http://dx.doi.org/10.1016/j.jcss.2016.09.002}, keywords = {Parameterized complexity; Kernelization; Nowhere dense graphs; Finite integer index; Treedepth}, language = {eng}, issn = {0022-0000}, journal = {Journal of Computer and System Sciences}, title = {Kernelization using structural parameters on sparse graph classes}, volume = {84}, year = {2017} }
TY - JOUR ID - 1372352 AU - Gajarský, Jakub - Hliněný, Petr - Obdržálek, Jan - Ordyniak, Sebastian - Reidl, Felix - Rossmanith, Peter - Villaamil, Fernando - Sikdar, Somnath PY - 2017 TI - Kernelization using structural parameters on sparse graph classes JF - Journal of Computer and System Sciences VL - 84 IS - 1 SP - 219-242 EP - 219-242 PB - Elsevier SN - 00220000 KW - Parameterized complexity KW - Kernelization KW - Nowhere dense graphs KW - Finite integer index KW - Treedepth N2 - We prove that graph problems with finite integer index have linear kernels on graphs of bounded expansion when parameterized by the size of a modulator to constant-treedepth graphs. For nowhere dense graph classes, our result yields almost-linear kernels. We also argue that such a linear kernelization result with a weaker parameter would fail to include some of the problems covered by our framework. We only require the problems to have FII on graphs of constant treedepth. This allows to prove linear kernels also for problems such as Longest-Path/Cycle, Exact-s, t-Path, Treewidth, and Pathwidth, which do not have FII on general graphs. (C) 2016 Elsevier Inc. All rights reserved. ER -
GAJARSKÝ, Jakub, Petr HLINĚNÝ, Jan OBDRŽÁLEK, Sebastian ORDYNIAK, Felix REIDL, Peter ROSSMANITH, Fernando VILLAAMIL a Somnath SIKDAR. Kernelization using structural parameters on sparse graph classes. \textit{Journal of Computer and System Sciences}. SAN DIEGO: Elsevier, 2017, roč.~84, č.~1, s.~219-242. ISSN~0022-0000. Dostupné z: https://dx.doi.org/10.1016/j.jcss.2016.09.002.
|