Extending Partial Representations of Interval Graphs

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Extending Partial Representations of Interval Graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Extending Partial Representations of Interval Graphs

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

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

Návaznosti

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

Rok uplatnění

2017

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 periodika

Algorithmica

ISSN

0178-4617

e-ISSN

—

Svazek periodika

70

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

23

Strana od-do

945-967

Kód UT WoS článku

000405494100008

EID výsledku v databázi Scopus

—