最小权度的网络构建问题

Network Construction Problem of Minmum Weighted Degree

网络构建问题是组合最优化中的经典问题,而连通性是网络设计问题中的一个核心问题。考虑这样一个最优化问题:给定无向图G=(V,E;w),w:E→Q^+是权重函数,G'=(V,E')为G的一个子图,要寻找E的一个子集E"(?)E,使得由E'UE"所得的诱导子图是一个连通图,其目标是使得所有方案中权度最大者的权度值达到最小。经过对问题分析,对问题的特殊情况E'=φ,设计了两个时间复杂度分别为O(n^2)和O(mn)的启发式算法,而E"≠φ的情况也可以类似讨论。

Network construction problem is a classic one in combinatorial optimization, and the connectivity problem is one of the most important problems in network construction. We consider the following optimization problem model： gives a nondigraph G＇=（V,E;w） and its subgraph G＇=（V, E＇）, w：E → Q^＋ is a cost-function. We are asked to find a subset E＂ CE, and the graph induced by E＇∪E＂ is connected. The object is to minimize the maximum cost of function wd （v）, where wd （v） is the weighted degree of vertex v. By analysing the problem, designs two heuristic algorithms to solve the special class of the problem if E＇≠ Ф, and the problem can be similarly solved ifE＇≠ Ф.