Balanced Degree Problem And Ratio Problem On A Network

Theories and methods of network optimization have infiltrated operational research, information theory, cybernetics, management science and computer science widely, and have very important applications in engineering technique and military affair etc. So carrying on an investigation in the effective algorithms of the diversified network optimization problems has been a theme of network optimization.In this paper, some new type network optimization problems are put forward and researched according to the practical background.Firstly, the balanced degree spanning tree problem is discussed. We investigate the minimum balanced degree spanning tree problem and the same problem contained settled edge set based on minimum spanning tree. Then the max-min spanning tree problem and the min-max spanning tree problem are also discussed.Secondly, we put forward two new type facility location problems. One is the minimum balanced degree facility location problem under star topology on plane and the other is the minimum balanced degree facility location problem on a network.Then, we construct a network model of the max-min spanning arborescence problem, we discuss the essential character of the max-min spanning arborescence and deduce an effective algorithm to solve this problem based on the relationship between the minimum in-arc circuit and the max-min spanning arborescence.At last, two ratio problems are discussed. The first is the minimum ratio spanning arborescence problem, and the second is the minimum ratio facility location problem on an undirected network.