2014
Finite Integer Index of Pathwidth and Treewidth
ORDYNIAK, Sebastian, Jakub GAJARSKÝ, Felix REIDL, Peter ROSSMANITH, Jan OBDRŽÁLEK et. al.Základní údaje
Originální název
Finite Integer Index of Pathwidth and Treewidth
Autoři
ORDYNIAK, Sebastian (276 Německo, garant, domácí), Jakub GAJARSKÝ (703 Slovensko, domácí), Felix REIDL (276 Německo), Peter ROSSMANITH (276 Německo), Jan OBDRŽÁLEK (203 Česká republika, domácí) a Fernando SÁNCHEZ VILAAMIL (724 Španělsko)
Vydání
Wroclaw, IPEC 2014, LNCS 8246, od s. 258-269, 12 s. 2014
Nakladatel
Springer
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
tištěná verze "print"
Impakt faktor
Impact factor: 0.402 v roce 2005
Kód RIV
RIV/00216224:14330/14:00077727
Organizační jednotka
Fakulta informatiky
ISBN
978-3-319-13523-6
ISSN
UT WoS
000354703200022
Klíčová slova anglicky
meta-kernalization; finite integer index; treewidth; pathwidth
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 16. 2. 2016 15:37, RNDr. Jakub Gajarský, Ph.D.
Anotace
V originále
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.
Návaznosti
| EE2.3.30.0009, projekt VaV |
|