Extending partial representations of subclasses of chordal graphs
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Extending partial representations of subclasses of chordal graphs
Original language description
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
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA14-14179S" target="_blank" >GA14-14179S: Algorithmic, structural and complexity aspects of configurations in the plane</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
—
Volume of the periodical
neuveden
Issue of the periodical within the volume
576
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
17
Pages from-to
85-101
UT code for WoS article
000353073000007
EID of the result in the Scopus database
2-s2.0-84930241571