Extending Partial Representations of Interval Graphs

Extending Partial Representations of Interval Graphs

0.00 Avg rating0 Votes
Article ID: iaor20173018
Volume: 78
Issue: 3
Start Page Number: 945
End Page Number: 967
Publication Date: Jul 2017
Journal: Algorithmica
Authors: , , , ,
Keywords: networks
Abstract:

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, the oldest one is by Booth and Lueker (J Comput Syst Sci 13:335–379, 1976) 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 equ1 fixing the positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation R equ2 of the entire graph G extending R equ3 . 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.

Reviews

Required fields are marked *. Your email address will not be published.