Finite Integer Index of Pathwidth and Treewidth

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

ORDYNIAK Sebastian GAJARSKÝ Jakub REIDL Felix ROSSMANITH Peter OBDRŽÁLEK Jan SÁNCHEZ VILAAMIL Fernando

Rok publikování 2014
Druh Článek ve sborníku
Konference IPEC 2014, LNCS 8246
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1007/978-3-319-13524-3_22
Obor Informatika
Klíčová slova meta-kernalization; finite integer index; treewidth; pathwidth
Popis We show that the optimization versions of the Pathwidth and Treewidth problems have a property called finite integer index when the inputs are restricted to graphs of bounded pathwidth and bounded treewidth, respectively. They do not have this property in general graph classes. This has interesting consequences for kernelization of both these (optimization) problems on certain sparse graph classes. In the process we uncover an interesting property of path and tree decompositions, which might be of independent interest.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.