Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph

For a graph GG in read-only memory on nn vertices and mm edges and a write-only output buffer, we give two algorithms using only O(n)O(n) rewritable space. The first algorithm lists all minimal a−ba−b separators of GG with a polynomial delay of O(nm)O(nm). The second lists all minimal vertex separators of GG with a cumulative polynomial delay of O(n3m)O(n3m).One consequence is that the algorithms can list the minimal a−ba−b separators (and minimal vertex separators) spending O(nm)O(nm) time (respectively, O(n3m)O(n3m) time) per object output.