Bounded Representations of Interval and Proper Interval Graphs
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Bounded Representations of Interval and Proper Interval Graphs
Original language description
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
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GEGIG%2F11%2FE023" target="_blank" >GEGIG/11/E023: Graph Drawings and Representations</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2013
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
Article name in the collection
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
—
Number of pages
12
Pages from-to
535-546
Publisher name
Springer Berlin Heidelberg
Place of publication
Neuveden
Event location
Hong Kong
Event date
Dec 16, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—