Given a graph G = (V, E) and a set of terminal vertices T we say that a superset S of T is T-connecting if S induces a connected graph, and S is minimal if no strict subset of S is T-connecting. In this paper we prove that there are at most (|VT| |T|-2) • 3 |VT|/3 minimal T-connecting sets when |T| ≤ n/3 and that these can be enumerated within a polynomial factor of this bound. This generalizes the algorithm for enumerating all induced paths between a pair of vertices, corresponding to the case |T| = 2. We apply our enumeration algorithm to solve the 2-Disjoint Connected Subgraphs problem in time O~*(1.7804~n), improving on the recent O~*(1.933~n) algorithm of Cygan et al. 2012 LATIN paper.
展开▼
机译：给定一个图G =（V，E）和一组终端顶点T，我们说如果S诱导一个连通图，则T的超集S是T-连接的，如果S的没有严格子集是T-连接的，则S最小。 。本文证明，当| T |时，最多存在（| V \ T | | T | -2）•3 | V \ T | / 3个最小T连接集。 ≤n / 3，并且可以在此范围的多项式因子内进行枚举。概括了用于枚举一对顶点之间的所有诱导路径的算法，对应于情况| T |。 =2。我们应用枚举算法在时间O〜*（1.7804〜n）的基础上解决了2不相交的连通子图问题，对Cygan等人最近的O〜*（1.933〜n）算法进行了改进。 2012拉丁纸。
展开▼
