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

An approximation algorithm for the min-max 2-path covering problem on{1,2}-weighted graphs

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

Given a{1,2}-weighted complete graph,the problem asks for two node-disjoint paths which together cover all vertices of the graph.The goal is to minimize the maximum path weight.By utilizing an existing algorithm for solving the traveling salesman problem on{1,2}-weighted graphs,we design an approximation algorithm for this problem and prove that the approximate ratio is no more than11/7.