Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1212629,
author = {Ordyniak, Sebastian and Gajarský, Jakub and Reidl, Felix and Rossmanith, Peter and Obdržálek, Jan and Sánchez Vilaamil, Fernando},
address = {Wroclaw},
booktitle = {IPEC 2014, LNCS 8246},
doi = {http://dx.doi.org/10.1007/978-3-319-13524-3_22},
editor = {Marek Cygan and Pinar Heggernes},
keywords = {meta-kernalization; finite integer index; treewidth; pathwidth},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Wroclaw},
isbn = {978-3-319-13523-6},
pages = {258-269},
publisher = {Springer},
title = {Finite Integer Index of Pathwidth and Treewidth},
year = {2014}
}
TY - JOUR
ID - 1212629
AU - Ordyniak, Sebastian - Gajarský, Jakub - Reidl, Felix - Rossmanith, Peter - Obdržálek, Jan - Sánchez Vilaamil, Fernando
PY - 2014
TI - Finite Integer Index of Pathwidth and Treewidth
PB - Springer
CY - Wroclaw
SN - 9783319135236
KW - meta-kernalization
KW - finite integer index
KW - treewidth
KW - pathwidth
N2 - 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.
ER -
ORDYNIAK, Sebastian, Jakub GAJARSKÝ, Felix REIDL, Peter ROSSMANITH, Jan OBDRŽÁLEK a Fernando SÁNCHEZ VILAAMIL. Finite Integer Index of Pathwidth and Treewidth. In Marek Cygan and Pinar Heggernes. \textit{IPEC 2014, LNCS 8246}. Wroclaw: Springer, 2014, s.~258-269. ISBN~978-3-319-13523-6. Dostupné z: https://dx.doi.org/10.1007/978-3-319-13524-3\_{}22.
|
