An O(n~2)-time Algorithm for the Minimal Interval Completion Problem

摘要

The minimal interval completion problem consists in adding edges to an arbitrary graph so that the resulting graph is an interval graph; the objective is to add an inclusion minimal set of edges, which means that no proper subset of the added edges can result in an interval graph when added to the original graph. We give an O(n~2)-time algorithm to obtain a minimal interval completion of an arbitrary graph. This improves the previous O(nm) time bound for the problem and lower this bound for the first time below the best known bound for minimal chordal completion.