Copy
Jiro HAYAKAWA, Shuji TSUKIYAMA, Hiromu ARIYOSHI, "Generation of Minimal Separating Sets of a Graph" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 5, pp. 775-783, May 1999, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_5_775/_p
Copy
@ARTICLE{e82-a_5_775,
author={Jiro HAYAKAWA, Shuji TSUKIYAMA, Hiromu ARIYOSHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Generation of Minimal Separating Sets of a Graph},
year={1999},
volume={E82-A},
number={5},
pages={775-783},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Generation of Minimal Separating Sets of a Graph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 775
EP - 783
AU - Jiro HAYAKAWA
AU - Shuji TSUKIYAMA
AU - Hiromu ARIYOSHI
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 1999
AB - 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.
ER -
English
