Series-Parallel图上最小权顶点覆盖3-路问题的有效算法

An efficient algorithm for the minimum weight vertex cover 3-path problem on Series-Parallel graphs

研究了Series-Parallel图上的顶点覆盖3-路问题,利用动态规划思想,给出一个能在多项式时间内完成的有效算法,该算法的运行时间为O(|V|)。

Given a vertex-weighted graph G=(V, E) and a positive integer k≥2, the minimum weight vertex cover k-path problem(MWVCPk) asks for a vertex subset F?V with minimum weight such that every path of order k contains at least one vertex from F. For any integer k≥2, MWVCPk on general graphs is NP-hard. In this paper, we study MWVCP3 on Series-Parallel graphs and present a dynamic programming algorithm with runtime O(|V|).