Completion of the Mixed Unit Interval Graphs Hierarchy

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-17142-5" target="_blank" >http://dx.doi.org/10.1007/978-3-319-17142-5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-17142-5" target="_blank" >10.1007/978-3-319-17142-5</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Completion of the Mixed Unit Interval Graphs Hierarchy

Popis výsledku v původním jazyce

We describe the missing class of the hierarchy of mixed unit interval graphs, generated by the intersection graphs of closed, open and one type of half-open intervals of the real line. This class lies strictly between unit interval graphs and mixed unitinterval graphs. We give a complete characterization of this new class, as well as a polynomial time algorithm to recognize graphs from this class and to produce a corresponding interval representation if one exists.

Název v anglickém jazyce

Completion of the Mixed Unit Interval Graphs Hierarchy

Popis výsledku anglicky

We describe the missing class of the hierarchy of mixed unit interval graphs, generated by the intersection graphs of closed, open and one type of half-open intervals of the real line. This class lies strictly between unit interval graphs and mixed unitinterval graphs. We give a complete characterization of this new class, as well as a polynomial time algorithm to recognize graphs from this class and to produce a corresponding interval representation if one exists.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

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 statě ve sborníku

Theory and Applications of Models of Computation

ISBN

978-3-319-17142-5

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

284-296

Název nakladatele

Springer

Místo vydání

New York

Místo konání akce

Singapore

Datum konání akce

18. 5. 2015

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

WRD - Celosvětová akce

Kód UT WoS článku

000361755700025