Number of the records: 1
Minimal Obstructions for Partial Representations of Interval Graphs
- 1.
SYSNO ASEP 0500501 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Minimal Obstructions for Partial Representations of Interval Graphs Author(s) Klavík, P. (CZ)
Saumell, Maria (UIVT-O) RID, SAI, ORCIDArticle number P4.55 Source Title Electronic Journal of Combinatorics. - : Electrochemical Society - ISSN 1077-8926
Roč. 25, č. 4 (2018)Number of pages 49 s. Language eng - English Country US - United States Keywords Interval graphs ; Partial representation extension ; PQ-trees ; Certifying algorithm Subject RIV BA - General Mathematics OECD category Pure mathematics R&D Projects GJ16-07822Y GA ČR - Czech Science Foundation (CSF) GBP202/12/G061 GA ČR - Czech Science Foundation (CSF) Institutional support UIVT-O - RVO:67985807 UT WOS 000456788300010 EID SCOPUS 85061618360 Annotation Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently. The input gives an interval graph with a partial representation specifying some pre-drawn intervals. We ask whether the remaining intervals can be added to create an extending representation. Two linear-time algorithms are known for solving this problem. In this paper, we characterize the minimal obstructions which make partial representations non-extendible. This generalizes Lekkerkerker and Boland's characterization of the minimal forbidden induced subgraphs of interval graphs. Each minimal obstruction consists of a forbidden induced subgraph together with at most four pre-drawn intervals. A Helly-type result follows: A partial representation is extendible if and only if every quadruple of pre-drawn intervals is extendible by itself. Our characterization leads to a linear-time certifying algorithm for partial representation extension. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2019 Electronic address https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p55
Number of the records: 1