## Abstract

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E). Our algorithm requires O(n^{3}R_{ab}) time, which improves the known result of O(n^{4}R_{ab}) time for solving this problem, where |V| = n and R_{ab} is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B ⊂ V, and it requires O(n^{2}(n - n_{A} - n_{B})R_{AB}) time in this case, where n_{A} = |A|, n_{B} = |B| and R_{AB} is the number of all minimal A-B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n^{3}R^{+}_{Σ} + n^{4}R_{Σ}), which improves the known result of O(n^{6}R_{Σ}) time, where R_{Σ} is the number of all minimal separators of G and R_{Σ} ≤ A^{+}_{Σ} = ∑_{1≤i≠j≤n,(vi,vj)∉E} R_{vivj} ≤ (n(n - 1)/2 - m)R_{Σ}. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_{ab}) time and the second one runs in time O((n/log n)R^{+}_{Σ} + n log nR_{Σ}) on a CREW PRAM with O(n^{3}) processors.

Original language | English |
---|---|

Pages (from-to) | 169-180 |

Number of pages | 12 |

Journal | Theoretical Computer Science |

Volume | 180 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - 10 Jun 1997 |

Externally published | Yes |