Bounded Representations of Interval and Proper Interval Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10190189" target="_blank" >RIV/00216208:11320/13:10190189 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/chapter/10.1007%2F978-3-642-45030-3_50" target="_blank" >http://link.springer.com/chapter/10.1007%2F978-3-642-45030-3_50</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-45030-3_50" target="_blank" >10.1007/978-3-642-45030-3_50</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Bounded Representations of Interval and Proper Interval Graphs

Popis výsledku v původním jazyce

Klavík et al. [arXiv:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper interval graphs. The input gives a graph G and in addition for each vertexv two intervals Lv and Rv called bounds. We ask whether there exists a bounded representation in which each interval Iv has its left endpoint in Lv and its right endpoint in Rv . We show that the problem can be solved in linear time for interval graphsand in quadratic time for proper interval graphs. Robert's Theorem states that the classes of proper interval graphs and unit interval graphs are equal. Surprisingly, the bounded representation problem is polynomially solvable for proper interval graphsand NP-complete for unit interval graphs [Klavík et al., arxiv:1207.6960]. So unless P = NP, the proper and unit interval representations behave very differently. The bounded representation problem belongs to a wider class of restricted r

Název v anglickém jazyce

Bounded Representations of Interval and Proper Interval Graphs

Popis výsledku anglicky

Klavík et al. [arXiv:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper interval graphs. The input gives a graph G and in addition for each vertexv two intervals Lv and Rv called bounds. We ask whether there exists a bounded representation in which each interval Iv has its left endpoint in Lv and its right endpoint in Rv . We show that the problem can be solved in linear time for interval graphsand in quadratic time for proper interval graphs. Robert's Theorem states that the classes of proper interval graphs and unit interval graphs are equal. Surprisingly, the bounded representation problem is polynomially solvable for proper interval graphsand NP-complete for unit interval graphs [Klavík et al., arxiv:1207.6960]. So unless P = NP, the proper and unit interval representations behave very differently. The bounded representation problem belongs to a wider class of restricted r

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GEGIG%2F11%2FE023" target="_blank" >GEGIG/11/E023: Kreslení grafů a jejich geometrické reprezentace</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2013

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

Algorithms and Computation 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings

ISBN

978-3-642-45029-7

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

535-546

Název nakladatele

Springer Berlin Heidelberg

Místo vydání

Neuveden

Místo konání akce

Hong Kong

Datum konání akce

16. 12. 2013

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

WRD - Celosvětová akce

Kód UT WoS článku

—