Extending Partial Representations of Interval Graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10368373" target="_blank" >RIV/00216208:11320/17:10368373 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1007/s00453-016-0186-z" target="_blank" >https://doi.org/10.1007/s00453-016-0186-z</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-016-0186-z" target="_blank" >10.1007/s00453-016-0186-z</a>

Result language

angličtina

Original language name

Extending Partial Representations of Interval Graphs

Original language description

Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition, asks whether an input graph G can be represented by closed intervals, i.e., whether G is an interval graph. There are several linear-time algorithms known for recognizing interval graphs, some are based on PQ-trees. In this paper, we study a generalization of recognition, called partial representation extension. The input of this problem consists of a graph G with a partial representation R&apos; fixing the positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation R of the entire graph G extending R&apos;. We generalize the characterization of interval graphs by Fulkerson and Gross (Pac J Math 15:835-855, 1965) to extendible partial representations. Using it, we give a linear-time algorithm for partial representation extension based on a reordering problem of PQ-trees.

Czech name

—

Czech description

—

Type

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

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)

Publication year

2017

Confidentiality

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

Name of the periodical

Algorithmica

ISSN

0178-4617

e-ISSN

—

Volume of the periodical

70

Issue of the periodical within the volume

3

Country of publishing house

US - UNITED STATES

Number of pages

23

Pages from-to

945-967

UT code for WoS article

000405494100008

EID of the result in the Scopus database

—