图的极小顶剖的有效枚举算法

Efficient Algorithms for Enumerating all Minimal Separators in a Graph

设G=(V,E)是无向连通单图,S为G的一个顶子集,G[S]为S的导出子图。若G[V-S]不连通,则称S为G的一个顶剖;若S是G的顶剖,而S的任意真子集都不是G的顶剖,则称S为G的一个极小顶剖。a,b为G中任意两个不相邻的顶,若a,b分别处在G[V-S]的不同连通片中,则称S是G的一个(a,b)顶剖;若S是G的(a,b)顶剖,而S的任意真子集都不是G的(a,b)顶剖,则称S为G的一个极小的(a,b)顶剖。枚举图中所有极小(a,b)顶剖和所有极小顶剖是图论中的一个基本枚举问题,这个问题在网络的可靠性分析和运筹学等方面有着极大的应用价值。

Enumerating all minimal separators of a graph is important in reliability analysis for networks and other areas. Given an undirected connected simple graph G= (V,E) and two non-adjacent vertices a and b,this paper presents two efficient algorithms for enumerating all minimal (a,b)separa-tors. All these two improve the known best results. Moreover,for two non-adjacent vertex sets A and B of G,we propose an algorithm to enumerating all minimal(A,B) separators.