Completion of the Mixed Unit Interval Graphs Hierarchy

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Completion of the Mixed Unit Interval Graphs Hierarchy

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2015

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Theory and Applications of Models of Computation

ISBN

978-3-319-17142-5

ISSN

0302-9743

e-ISSN

—

Number of pages

13

Pages from-to

284-296

Publisher name

Springer

Place of publication

New York

Event location

Singapore

Event date

May 18, 2015

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000361755700025