Detailed Information on Publication Record
2014
Finite Integer Index of Pathwidth and Treewidth
ORDYNIAK, Sebastian, Jakub GAJARSKÝ, Felix REIDL, Peter ROSSMANITH, Jan OBDRŽÁLEK et. al.Basic information
Original name
Finite Integer Index of Pathwidth and Treewidth
Authors
ORDYNIAK, Sebastian (276 Germany, guarantor, belonging to the institution), Jakub GAJARSKÝ (703 Slovakia, belonging to the institution), Felix REIDL (276 Germany), Peter ROSSMANITH (276 Germany), Jan OBDRŽÁLEK (203 Czech Republic, belonging to the institution) and Fernando SÁNCHEZ VILAAMIL (724 Spain)
Edition
Wroclaw, IPEC 2014, LNCS 8246, p. 258-269, 12 pp. 2014
Publisher
Springer
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
United States of America
Confidentiality degree
není předmětem státního či obchodního tajemství
Publication form
printed version "print"
Impact factor
Impact factor: 0.402 in 2005
RIV identification code
RIV/00216224:14330/14:00077727
Organization unit
Faculty of Informatics
ISBN
978-3-319-13523-6
ISSN
UT WoS
000354703200022
Keywords in English
meta-kernalization; finite integer index; treewidth; pathwidth
Tags
International impact, Reviewed
Změněno: 16/2/2016 15:37, RNDr. Jakub Gajarský, Ph.D.
Abstract
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.
Links
| EE2.3.30.0009, research and development project |
|