کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429966 | 687756 | 2016 | 15 صفحه PDF | دانلود رایگان |
• A unified tradeoff-based approach for computing representative families.
• Faster FPT algorithms for problems previously solved by using representative families.
• Fastest FPT algorithm for the k-Partial Cover problem.
• Faster deterministic FPT algorithm for the k-Internal Out-Branching problem.
Given a matroid M=(E,I)M=(E,I), and a family SS of p-subsets of E , a subfamily Sˆ⊆S represents SS if for any X∈SX∈S and Y⊆E∖XY⊆E∖X satisfying X∪Y∈IX∪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.
Journal: Journal of Computer and System Sciences - Volume 82, Issue 3, May 2016, Pages 488–502