About: Kernelization Using Structural Parameters on Sparse Graph Classes

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Kernelization Using Structural Parameters on Sparse Graph Classes Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	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. 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. (en)
Title	Kernelization Using Structural Parameters on Sparse Graph Classes Kernelization Using Structural Parameters on Sparse Graph Classes (en)
skos:prefLabel	Kernelization Using Structural Parameters on Sparse Graph Classes Kernelization Using Structural Parameters on Sparse Graph Classes (en)
skos:notation	RIV/00216224:14330/13:00066378!RIV14-MSM-14330___
http://linked.open...avai/riv/aktivita	P S
http://linked.open...avai/riv/aktivity	P(EE2.3.30.0009), P(GAP202/11/0196), S
http://linked.open...vai/riv/dodaniDat	2014
http://linked.open...aciTvurceVysledku	Obdržálek, Jan Hliněný, Petr Gajarský, Jakub Ordyniak, Sebastian
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	82608
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/13:00066378
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	kernelization; parameterized complexity; sparse graphs (en)
http://linked.open.../riv/klicoveSlovo	parameterized complexity sparse graphs kernelization
http://linked.open...ontrolniKodProRIV	[87A3872E6D43]
http://linked.open...v/mistoKonaniAkce	Sophia Antipolis, France
http://linked.open...i/riv/mistoVydani	Berlin Heidelberg
http://linked.open...i/riv/nazevZdroje	ESA 2013
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	4 (xsd:int)
http://linked.open...cetTvurcuVysledku	8 (xsd:int)
http://linked.open...vavai/riv/projekt	Well-structured combinatorial classes, width parameters, and design of efficient algorithms Employment of Newly Graduated Doctors of Science for Scientific Excellence
http://linked.open...UplatneniVysledku	2013
http://linked.open...iv/tvurceVysledku	Hliněný, Petr Obdržálek, Jan Rossmanith, Peter Ordyniak, Sebastian Gajarský, Jakub Sikdar, Somnath Reidl, Felix Villaamil, Fernando Sanchez
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2013-01-01 (xsd:date)
issn	0302-9743
number of pages	12 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/978-3-642-40450-4_45
http://purl.org/ne...btex#hasPublisher	Springer-Verlag
https://schema.org/isbn	9783642404498
http://localhost/t...ganizacniJednotka	14330

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software