论文标题
查找$ k $ - 陈旧的树木更快
Finding $k$-Secluded Trees Faster
论文作者
论文摘要
我们重新访问\ textsc {$ k $ -secluded tree}问题。鉴于顶点加权的无向图$ g $，其目标是找到一个最大权重的子树$ t $，其开放式邻居最多具有$ k $。我们提出了一个固定参数可处理算法，该算法在时间中解决问题$ 2^{\ Mathcal {o}（k \ log k）} \ cdot n^{\ nathcal {\ Mathcal {o}（1）} $，在Goolovach，Heggerne，Heggerne，Lima，monte，Mont和mont的较早的工作中改善了较早的运行时间。从单个顶点开始，我们的算法通过在当前树$ t $的开放社区的顶点上分支在顶点上种植了$ k $ secluded的树。为了束缚分支深度，我们证明了一个结构性结果，该结果可用于识别属于任何$ k $ -secluded supertree $ t'\ supseteq t $的顶点，一旦$ t $的开放社区变得足够大。我们扩展了算法以列举所有最大重量$ k $ secluded树的紧凑描述，这使我们能够在同一运行时间内计算包含指定顶点的最大重量$ k $ secluded树的数量。
We revisit the \textsc{$k$-Secluded Tree} problem. Given a vertex-weighted undirected graph $G$, its objective is to find a maximum-weight induced subtree $T$ whose open neighborhood has size at most $k$. We present a fixed-parameter tractable algorithm that solves the problem in time $2^{\mathcal{O}(k \log k)}\cdot n^{\mathcal{O}(1)}$, improving on a double-exponential running time from earlier work by Golovach, Heggernes, Lima, and Montealegre. Starting from a single vertex, our algorithm grows a $k$-secluded tree by branching on vertices in the open neighborhood of the current tree $T$. To bound the branching depth, we prove a structural result that can be used to identify a vertex that belongs to the neighborhood of any $k$-secluded supertree $T' \supseteq T$ once the open neighborhood of $T$ becomes sufficiently large. We extend the algorithm to enumerate compact descriptions of all maximum-weight $k$-secluded trees, which allows us to count the number of maximum-weight $k$-secluded trees containing a specified vertex in the same running time.
