在圈图上研究了两类组合优化问题．第一类问题主要研究在要求图中各边的最大调整费用不能超过给定预算时，如何对各边权进行调整，使得其他各顶点到给定顶点的距离之和最大，得到了线性时间算法；第二类问题主要研究在要求圈图上的所有边的调整费用之和不超过给定预算时，如何对各边权进行调整，使得某一固定顶点到给定顶点的距离尽可能的大，得到了求解该问题的多项式时间算法．
中国计量大学学报
2017年2期
