Finite Integer Index of Pathwidth and Treewidth

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Finite Integer Index of Pathwidth and Treewidth

Popis výsledku v původním jazyce

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ázev v anglickém jazyce

Finite Integer Index of Pathwidth and Treewidth

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci</a><br>

Návaznosti

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

Rok uplatnění

2014

Kód důvěrnosti údajů

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

Název statě ve sborníku

Lecture Notes in Computer Science

ISBN

9783319135236

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

258-269

Název nakladatele

Springer

Místo vydání

Wroclaw

Místo konání akce

Wroclaw

Datum konání akce

10. 9. 2014

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—