All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Completion of the mixed unit interval graphs hierarchy

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10386652" target="_blank" >RIV/00216208:11320/18:10386652 - isvavai.cz</a>

  • Result on the web

    <a href="https://doi.org/10.1002/jgt.22159" target="_blank" >https://doi.org/10.1002/jgt.22159</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1002/jgt.22159" target="_blank" >10.1002/jgt.22159</a>

Alternative languages

  • 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. This class is generated by the intersection graphs of families of unit intervals that are allowed to be closed, open, and left-closed-right-open. (By symmetry, considering closed, open, and right-closed-left-open unit intervals generates the same class.) We show that this class lies strictly between unit interval graphs and mixed unit interval graphs. We give a complete characterization of this new class, as well as quadratic-time algorithms that recognize graphs from this class and produce a corresponding interval representation if one exists. We also show that the algorithm from Shuchat et al. [8] directly extends to provide a quadratic-time algorithm to recognize the class of mixed unit interval graphs.

  • Czech name

  • Czech description

Classification

  • Type

    J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database

  • CEP classification

  • OECD FORD branch

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Result continuities

  • 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

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Others

  • Publication year

    2018

  • 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

    Journal of Graph Theory

  • ISSN

    0364-9024

  • e-ISSN

  • Volume of the periodical

    87

  • Issue of the periodical within the volume

    3

  • Country of publishing house

    US - UNITED STATES

  • Number of pages

    16

  • Pages from-to

    317-332

  • UT code for WoS article

    000428550700005

  • EID of the result in the Scopus database

    2-s2.0-85020310183