Home > News > Maria Saumell: Extending Partial Representations of Proper and Unit Interval Graphs

Maria Saumell: Extending Partial Representations of Proper and Unit Interval Graphs

Date: 10. 12. 2012
Source: Graph theory and algorithms seminar
ńĆetrtek 13.12.2012 ob 12:15 v predavalnici 3.05 na Jadranski 21
A recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether it is possible to extend this partial representation to the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations.