Menu
A well-known subclass of chordal graphs is formed by proper interval graphs. Due to their very special structural properties, several problems proved hard to solve for interval graphs can have better solutions for this subclass. In this paper, we address the recognition problem, proposing an update of one of the first existing linear algorithms. The outcome is a simple and efficient algorithm. In addition, we present a certifying algorithm for the recognition of proper interval graphs