Representative families: A unified tradeoff-based approach
Representative families: A unified tradeoff-based approach
复制标题
DOI：
10.1016/j.jcss.2015.11.008
复制
发表时间：
2014-02
期刊：
影响因子：
--
通讯作者：
H. Shachnai;M. Zehavi
中科院分区：
文献类型：
--
作者：
H. Shachnai;M. Zehavi
给定一个拟阵 M=(E, I) 和 E 的 p 子集的族 S，子族 S ˆ⊆ S 表示 S，如果对于任何 X∈ S 和 Y⊆ E∖ X 满足 X∪ Y∈ I，则存在一个与 Y 不相交的集合 X ˆ∈ S ˆ，其中 X ˆ∪ Y∈ I。我们展示了由 Fomin 等人引入的一种用于计算代表性族的强大技术al.(2014)[5] 提出了一种统一的方法，可以显着改善一些经典问题的参数化算法的运行时间。这包括 k-部分覆盖、k-内部分支和长有向循环等。我们的方法利用了运行时间和代表性家庭规模之间的有趣权衡。
Given a matroid M=(E, I), and a family S of p-subsets of E, a subfamily S ˆ⊆ S represents S if for any X∈ S and Y⊆ E∖ X satisfying X∪ Y∈ I, there is a set X ˆ∈ S ˆ disjoint from Y, where X ˆ∪ Y∈ I. We show that a powerful technique for computing representative families, introduced by Fomin et al.(2014)[5], leads to a unified approach for substantially improving the running times of parameterized algorithms for some classic problems. This includes k-Partial Cover, k-Internal Out-Branching, and Long Directed Cycle, among others. Our approach exploits an interesting tradeoff between running time and the representative family size.