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

Generating all the Minimal Separators of a Graph
 
 
 

Abstract:

  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