Publikace na Matematicko-fyzikální fakulta |
2011
Abstrakt
We initiate the study of the computational complexity of the question of extending partial representations of geometric intersection graphs. In this paper we consider classes of interval graphs - given a collection of real intervals that forms an intersection representation of an induced subgraph of an input graph, is it possible to add intervals to achieve an intersection representation of the entire graph? We present an O(n^2) time algorithm that solves this problem and constructs a representation if one exists.
Our algorithm can also be used to list all nonisomorphic extensions with O(n^2) delay.