TY - JOUR

T1 - Efficient enumeration of all minimal separators in a graph

AU - Shen, Hong

AU - Liang, Weifa

N1 - Funding Information:
author. E-mail: [email protected]. partially supported by Australia Research Council under its Small Grants Scheme

PY - 1997/6/10

Y1 - 1997/6/10

N2 - 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(n3Rab) time, which improves the known result of O(n4Rab) time for solving this problem, where |V| = n and Rab 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(n2(n - nA - nB)RAB) time in this case, where nA = |A|, nB = |B| and RAB 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(n3R+Σ + n4RΣ), which improves the known result of O(n6RΣ) time, where RΣ is the number of all minimal separators of G and RΣ ≤ A+Σ = ∑1≤i≠j≤n,(vi,vj)∉E Rvivj ≤ (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)Rab) time and the second one runs in time O((n/log n)R+Σ + n log nRΣ) on a CREW PRAM with O(n3) processors.

AB - 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(n3Rab) time, which improves the known result of O(n4Rab) time for solving this problem, where |V| = n and Rab 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(n2(n - nA - nB)RAB) time in this case, where nA = |A|, nB = |B| and RAB 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(n3R+Σ + n4RΣ), which improves the known result of O(n6RΣ) time, where RΣ is the number of all minimal separators of G and RΣ ≤ A+Σ = ∑1≤i≠j≤n,(vi,vj)∉E Rvivj ≤ (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)Rab) time and the second one runs in time O((n/log n)R+Σ + n log nRΣ) on a CREW PRAM with O(n3) processors.

UR - http://www.scopus.com/inward/record.url?scp=0031163960&partnerID=8YFLogxK

U2 - 10.1016/S0304-3975(97)83809-1

DO - 10.1016/S0304-3975(97)83809-1

M3 - Article

AN - SCOPUS:0031163960

SN - 0304-3975

VL - 180

SP - 169

EP - 180

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -