ORDYNIAK, Sebastian, Jakub GAJARSKÝ, Felix REIDL, Peter ROSSMANITH, Jan OBDRŽÁLEK and Fernando SÁNCHEZ VILAAMIL. Finite Integer Index of Pathwidth and Treewidth. In Marek Cygan and Pinar Heggernes. IPEC 2014, LNCS 8246. Wroclaw: Springer. p. 258-269. ISBN 978-3-319-13523-6. doi:10.1007/978-3-319-13524-3_22. 2014.
Other formats:   BibTeX LaTeX RIS
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
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
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 0302-9743
Doi http://dx.doi.org/10.1007/978-3-319-13524-3_22
UT WoS 000354703200022
Keywords in English meta-kernalization; finite integer index; treewidth; pathwidth
Tags firank_B
Tags International impact, Reviewed
Changed by Changed by: RNDr. Jakub Gajarský, Ph.D., učo 172462. Changed: 16/2/2016 15:37.
Abstract
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 projectName: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci
PrintDisplayed: 29/3/2024 03:17