On minimal augmentation of a graph to obtain an interval graph

摘要

This paper deals with the problem of adding edges to a graph such that the resulting graph becomes an interval graph. The set of edges added is called an augmentation. An algorithm is presented to find a minimal augmentation which runs in a time proportional to the product of the number of vertices and the number of edges of the resulting graph.