Research On Several Network Optimization Problems Of Cycles And Trees

Network optimization is an important branch of operations re-search and theoretical computer science,it has a wide range of applications in transportation,logistics management,communication network,and oth-er fields.In the research of network optimization,we hope to find the polynomial time algorithm.But when a network optimization problem is an NP-hard problem,we should prove that the problem is NP-hard firstly,then we are devoted to finding a polynomial time algorithm for the problem on a special condition.In this paper,we focus on several kinds of network optimization problems related to cycles and trees.Details are as follows.Firstly,we considered a kind of network optimization problem on cy-cles.Assume that the vertex number of the cycle is n,in this kind of net-work optimization problem,we mainly considered how to adjust the weight of each edge,such that the maximum adjusted cost of each edge does not exceed the given budget,and the sum of the distances from all the other vertices to the given vertex is maximum.We obtained a linear time algo-rithm of complexity O(n).Moreover,we solved instances of this problem and implemented it by C++ program.Secondly,we considered the other kind of network optimization prob-lem on cycles.Assume that the vertex number of the cycle is n,we mainly considered how to adjust the edge weights,such that the total adjusted cost of each edge does not exceed the given budget,and the distance from a fixed vertex to the given vertex is maximum.We obtained a polynomial time algorithm of complexity O(n log n).We verified the effectiveness of the algorithm by instances and program of this problem.Thirdly,we considered the balanced spanning tree problems of the net-work.Assume that E is the edge set and the number of edges of the network is |E|,combining with the practical logistics network optimization problem-s,we studied the most balanced spanning tree problems in networks,and presented polynomial time algorithms of complexity O(|E|2 log |E|).Based on the most balanced spanning tree problems,we studied the most unbal-anced spanning tree problems of the network,and proposed polynomial time algorithm of complexity O(|E|).Finally,we studied a kind of the most optimal subtree problem of the network.By transforming the connected dominating set problem into the optimal subtree problem,we proved that the most optimal subtree problem of a network is also NP-hard even when the weight of each edge is unit.Moreover,we characterized the optimal subtrees of four kinds of special networks.