The search functionality is under construction.

The search functionality is under construction.

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, 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*(µ(*m**t*(*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*(*m**n*α(*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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

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 *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, 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*(µ(*m**t*(*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*(*m**n*α(*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 *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, 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*(µ(*m**t*(*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*(*m**n*α(*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 *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, 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*(µ(*m**t*(*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*(*m**n*α(*n*)) time per s-t separating set, where α(*n*) is the pseudo-inverse of Ackermann function.

ER -