Generation of Minimal Separating Sets of a Graph (Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
For given undirected graph G=[V, E] and vertices s and t, a minimal s-t separating set denoted by E_c & V_c is a minimal set of elements (edges and/or vertices) such that deletion of the elements from G breaks all the paths between s and t, where E_c and V_c are sets of edges and vertices, respec tively. In this paper, we consider a problem of generating all minimal s-t separating sets, and show that the problem can be solved in O(μ(m + t(n,n))) time, where m=|E|, n=|U|, μ is the number of minimal s-t separating sets of G, and t(p, q) is the time needed for finding q lowest common ancestors for q pairs of vertices in a rooted tree with p vertices. Since t(n, n) can be O(n), we can generate all minimal s-t separating in linear time per s-t separating set. However, the linear time algorithm for finding the lowest common ancestors is complicated, so that it is not efficient for a moderate size graph. Therefore, we use an O(nα(n))-time algorithm for finding the lowest common ancestors, and propose an algorithm to generate all minimal s-t separating sets in O(m + nα(n)) time per s-t separating set, where α(n) is the pseudo-inverse of Ackermann function.
社団法人電子情報通信学会の論文
1999-05-25