A. Berry,  J-P Bordat, O. Cogis 

Generating all the Minimal Separators of a Graph


  We present an efficient algorithm which computes the set of minimal separators of a graph in O(n3) time per separator, thus gaining a factor of n2 on the current best-time algorithms for this problem.
  Our process is based on a new structural result, derived from Kloks and Kratsch' work on listing all the minimal separators of a graph.

 full postscript version

Home page           Publications and Research Reports           Our Research Topics