Efficient enumeration of all minimal separators in a graph |
| |
Authors: | Hong Shen Weifa Liang |
| |
Affiliation: | a School of Computing and Information Technology, Griffith University, Nathan, QLD 4111, Australia b Department of Computer Science, Australian National University, Canberra, ACT 0200, Australia |
| |
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(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ΣR+Σ = ∑1i, vj) ERvivj (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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|