Finite Integer Index of Pathwidth and Treewidth

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F14%3A00077727" target="_blank" >RIV/00216224:14330/14:00077727 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/978-3-319-13524-3_22" target="_blank" >http://dx.doi.org/10.1007/978-3-319-13524-3_22</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-13524-3_22" target="_blank" >10.1007/978-3-319-13524-3_22</a>

Result language

angličtina

Original language name

Finite Integer Index of Pathwidth and Treewidth

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Employment of Newly Graduated Doctors of Science for Scientific Excellence</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2014

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Lecture Notes in Computer Science

ISBN

9783319135236

ISSN

0302-9743

e-ISSN

—

Number of pages

12

Pages from-to

258-269

Publisher name

Springer

Place of publication

Wroclaw

Event location

Wroclaw

Event date

Sep 10, 2014

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—