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.
翻译：让 G$ 成为 $n 的顶点图, $, t $, t ods 。 我们提出了一个高效的算法, 将最低 $- separators 的集合量按基本值的升序计算, 延迟为 $( n ⁇ 3.5 } ) 美元 。 特别是, 我们提出了一个算法, 以最基本值的升序列出所有最低 的 separators, 最多为 $k$ 。 在此情况下, 我们显示查点算法的延迟是 $( kn ⁇ 2.5 } ) 。 我们的程序基于一种新的方法, 在多指标时间里, 可以决定特定包容、 排斥 和 基点限制 下的最低 分隔器的设定值是否为空 。
相关内容
微信扫码咨询专知VIP会员