Kernelization using structural parameters on sparse graph classes
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F17%3A00094632" target="_blank" >RIV/00216224:14330/17:00094632 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.jcss.2016.09.002" target="_blank" >http://dx.doi.org/10.1016/j.jcss.2016.09.002</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jcss.2016.09.002" target="_blank" >10.1016/j.jcss.2016.09.002</a>
Alternative languages
Result language
angličtina
Original language name
Kernelization using structural parameters on sparse graph classes
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA14-03501S" target="_blank" >GA14-03501S: Parameterized algorithms and kernelization in the context of discrete mathematics and logic</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Computer and System Sciences
ISSN
0022-0000
e-ISSN
—
Volume of the periodical
84
Issue of the periodical within the volume
1
Country of publishing house
US - UNITED STATES
Number of pages
24
Pages from-to
219-242
UT code for WoS article
000388430000015
EID of the result in the Scopus database
2-s2.0-84995685584