圈图上的两类组合优化问题  

Two combinatorial optimization problems on cycles

作　　者：杨晓兵[1] 王勤[1] 

机构地区：[1]中国计量大学理学院,浙江杭州310018

出　　处：《中国计量大学学报》2017年第2期247-251,共5页Journal of China University of Metrology

基　　金：国家自然科学基金资助项目(No.11171316)

摘　　要：在圈图上研究了两类组合优化问题.第一类问题主要研究在要求图中各边的最大调整费用不能超过给定预算时,如何对各边权进行调整,使得其他各顶点到给定顶点的距离之和最大,得到了线性时间算法;第二类问题主要研究在要求圈图上的所有边的调整费用之和不超过给定预算时,如何对各边权进行调整,使得某一固定顶点到给定顶点的距离尽可能的大,得到了求解该问题的多项式时间算法.Two combinatorial optimization problems were studied on cycle graphs. One was how to adjust the weight of each edge to avoid the cost of each edge exceeding the given budget, to adjust the sum of distances from all the other vertices to the maximum. A linear-time algorithm was proposed. The other problem was to adjust the edge weights to avoid the cost of each edge exceeding the given budget, and to adjust the distance from a fixed vertex to the given vertex to the maximum. A polynomial-time algorithm was also presented in this case.

关 键 词：圈图 组合优化问题 多项式时间算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] O221[自动化与计算机技术—计算机科学与技术]