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

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