{1,2}-赋权图最小最大2-路径覆盖问题的近似算法

作者：姚会影; 周圆; 陈光亭; 陈永^*; 张安

来源：杭州电子科技大学学报(自然科学版), 2022, 42(05): 89-92.

DOI：10.13954/j.cnki.hdu.2022.05.014

• {1,2}-赋权图
• 路径覆盖
• 旅行售货商问题
• 近似算法

给定边权重为1或2的完全图，研究如何用2条顶点不相交的路径覆盖图中所有顶点，为了达到最大路径权重尽可能小的目标，在{1,2}-赋权图上旅行售货商问题的已有算法的基础上，设计了该问题的近似算法，并证明了算法的近似比不超过■。

• 单位
  杭州电子科技大学; 台州学院