Extending partial representations of subclasses of chordal graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10316695" target="_blank" >RIV/00216208:11320/15:10316695 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.tcs.2015.02.007" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2015.02.007</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2015.02.007" target="_blank" >10.1016/j.tcs.2015.02.007</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Extending partial representations of subclasses of chordal graphs

Popis výsledku v původním jazyce

Chordal graphs are intersection graphs of subtrees of a tree T. We investigate the complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T' and some pre-drawn subtrees of T'. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (i.e., keeps the pre-drawn subtrees unchanged). We consider four modifications of T' leading to vastly different problems: (i) T = T', (ii)T is a subdivision of T', (iii) T is a supergraph of T', and (iv) T' is a topological minor of T. In some cases, it is interesting to consider the complexity even when just T' is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization. We further study the parametrized complexity of the problems when parametrized by the number of pre

Název v anglickém jazyce

Extending partial representations of subclasses of chordal graphs

Popis výsledku anglicky

Chordal graphs are intersection graphs of subtrees of a tree T. We investigate the complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T' and some pre-drawn subtrees of T'. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (i.e., keeps the pre-drawn subtrees unchanged). We consider four modifications of T' leading to vastly different problems: (i) T = T', (ii)T is a subdivision of T', (iii) T is a supergraph of T', and (iv) T' is a topological minor of T. In some cases, it is interesting to consider the complexity even when just T' is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization. We further study the parametrized complexity of the problems when parametrized by the number of pre

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA14-14179S" target="_blank" >GA14-14179S: Algoritmické, strukturální a složitostní aspekty konfigurací v rovině</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

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 periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

neuveden

Číslo periodika v rámci svazku

576

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

17

Strana od-do

85-101

Kód UT WoS článku

000353073000007

EID výsledku v databázi Scopus

2-s2.0-84930241571