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

作者：张文杰; 涂建华^*

来源：北京化工大学学报(自然科学版), 2019, 46(01): 124-128.

DOI：10.13543/j.bhxbzr.2019.01.019

• Series-Parallel图
• 顶点覆盖k-路问题
• 有效算法
• 动态规划

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

• 单位
  北京化工大学