Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1123296, author = {Gajarský, Jakub and Hliněný, Petr and Obdržálek, Jan and Ordyniak, Sebastian and Reidl, Felix and Rossmanith, Peter and Villaamil, Fernando Sanchez and Sikdar, Somnath}, address = {Berlin Heidelberg}, booktitle = {ESA 2013}, doi = {http://dx.doi.org/10.1007/978-3-642-40450-4_45}, editor = {Hans L. Bodlaender a Giuseppe F. Italiano}, keywords = {kernelization; parameterized complexity; sparse graphs}, howpublished = {tištěná verze "print"}, language = {eng}, location = {Berlin Heidelberg}, isbn = {978-3-642-40449-8}, pages = {529-540}, publisher = {Springer}, title = {Kernelization Using Structural Parameters on Sparse Graph Classes}, year = {2013} }
TY - JOUR ID - 1123296 AU - Gajarský, Jakub - Hliněný, Petr - Obdržálek, Jan - Ordyniak, Sebastian - Reidl, Felix - Rossmanith, Peter - Villaamil, Fernando Sanchez - Sikdar, Somnath PY - 2013 TI - Kernelization Using Structural Parameters on Sparse Graph Classes PB - Springer CY - Berlin Heidelberg SN - 9783642404498 KW - kernelization KW - parameterized complexity KW - sparse graphs N2 - Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, there were meta-theorems for linear kernels on graphs of bounded genus, H-minor-free graphs, and H-topological-minor-free graphs. To the best of our knowledge, there are no known meta-theorems for kernels for any of the larger sparse graph classes: graphs of bounded expansion, locally bounded expansion, and nowhere dense graphs. In this paper we prove meta-theorems for these three graph classes. More specifically, we show that graph problems that have finite integer index (FII) admit linear kernels on hereditary graphs of bounded expansion when parameterized by the size of a modulator to constant-treedepth graphs. For hereditary graph classes of locally bounded expansion, our result yields a quadratic kernel and for hereditary nowhere dense graphs, a polynomial kernel. While our parameter may seem rather strong, a linear kernel result on graphs of bounded expansion with a weaker parameter would for some problems violate known lower bounds. Moreover, we use a relaxed notion of FII which allows us to prove linear kernels for problems such as Longest Path/Cycle and Exact s,t-Path which do not have FII in general graphs. ER -
GAJARSKÝ, Jakub, Petr HLINĚNÝ, Jan OBDRŽÁLEK, Sebastian ORDYNIAK, Felix REIDL, Peter ROSSMANITH, Fernando Sanchez VILLAAMIL a Somnath SIKDAR. Kernelization Using Structural Parameters on Sparse Graph Classes. In Hans L. Bodlaender a Giuseppe F. Italiano. \textit{ESA 2013}. Berlin Heidelberg: Springer, 2013, s.~529-540. ISBN~978-3-642-40449-8. Dostupné z: https://dx.doi.org/10.1007/978-3-642-40450-4\_{}45.
|