The search functionality is under construction.
The search functionality is under construction.

Generation of Minimal Separating Sets of a Graph

Jiro HAYAKAWA, Shuji TSUKIYAMA, Hiromu ARIYOSHI

  • Full Text Views

    0

  • Cite this

Summary :

For given undirected graph G[V,E] and vertices s and t, a minimal s-t separating set denoted by Ec & Vc 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 Ec and Vc are sets of edges and vertices, respectively. 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(µ(mt(n,n))) time, where m|E|, n|V|, µ 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(mnα(n)) time per s-t separating set, where α(n) is the pseudo-inverse of Ackermann function.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.5 pp.775-783
Publication Date
1999/05/25
Publicized
Online ISSN
DOI
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category

Authors

Keyword