Representative families: A unified tradeoff-based approach

作者：

Highlights：

• 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.

摘要

•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.

论文关键词：k-PC,k-Partial Cover,k-IOB,k-Internal Out-Branching,Parameterized algorithm,Representative family,Uniform matroid,k-Partial cover,k-Internal out-branching

论文评审过程：Received 10 August 2014, Revised 15 November 2015, Accepted 20 November 2015, Available online 27 November 2015, Version of Record 29 December 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.11.008