Extending Partial Representations of Function Graphs and Permutation Graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10131345" target="_blank" >RIV/00216208:11320/12:10131345 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/978-3-642-33090-2_58" target="_blank" >http://dx.doi.org/10.1007/978-3-642-33090-2_58</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-33090-2_58" target="_blank" >10.1007/978-3-642-33090-2_58</a>

Result language

angličtina

Original language name

Extending Partial Representations of Function Graphs and Permutation Graphs

Original language description

Function graphs are graphs representable by intersections of continuous real-valued functions on the interval [0,1] and are known to be exactly the complements of comparability graphs. As such they are recognizable in polynomial time. Function graphs generalize permutation graphs, which arise when all functions considered are linear. We focus on the problem of extending partial representations, which generalizes the recognition problem. We observe that for permutation graphs an easy extension of Golumbic's comparability graph recognition algorithm can be exploited. This approach fails for function graphs. Nevertheless, we present a polynomial-time algorithm for extending a partial representation of a graph by functions defined on the entire interval [0,1] provided for some of the vertices. On the other hand, we show that if a partial representation consists of functions defined on subintervals of [0,1], then the problem of extending this representation to functions on the entire interv

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/GEGIG%2F11%2FE023" target="_blank" >GEGIG/11/E023: Graph Drawings and Representations</a><br>

Continuities

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

Publication year

2012

Confidentiality

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

Name of the periodical

Lecture Notes in Computer Science

ISSN

0302-9743

e-ISSN

—

Volume of the periodical

7501

Issue of the periodical within the volume

Fall

Country of publishing house

DE - GERMANY

Number of pages

12

Pages from-to

671-682

UT code for WoS article

—

EID of the result in the Scopus database

—