Enumerating Minimal Separators in Ranked Order

11/15/2021
by   Batya Kenig, et al.
0

Let G be an n-vertex graph, and s,t vertices of G. We present an efficient algorithm which enumerates the set of minimal st-separators of G in ascending order of cardinality, with a delay of O(n^3.5) per separator. In particular, we present an algorithm that lists, in ascending order of cardinality, all minimal separators with at most k vertices. In that case, we show that the delay of the enumeration algorithm is O(kn^2.5) per separator. Our process is based on a new method that can decide, in polynomial time, whether the set of minimal separators under certain inclusion, exclusion, and cardinality constraints is empty.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset