P123: Enumeration of Proper Interval Graphs

P123: Enumeration of Proper Interval Graphs

Input:

An integer $n$.

Output:

All proper interval graphs with $n$ vertices.

Complexity:

$O(1)$ time per proper interval graph and $O(n)$ space, after $O(n^2)$ preprocessing time.

Comment:

Preprocessing: generating the complete graph with $n$ vertices.

Reference:

[Saitoh2010a] (Bibtex)