The Algorithms And Complexities Of Several Network Improvement Problems

Network improvement problem is a hot topic in the field ofinverse network optimization theory. The shortest path improvement prob-lemisanimportantbranchofnetworkimprovementproblemsandiswidelystudied. It deals with how to change the parameters in the network, so thatthe shortest distances of the given vertices satisfy the given upper bound-s, and the modification cost is minimum. On the general network, mostshortest path improvement problems are strongly NP-hard, except the oneon the l∞norm, which can be solved in polynomial time. So many re-searchers have studied the shortest path improvement problem on specialnetwork structures.Under the l1norm, the shortest path improvement problem on a treeis polynomial-time solvable. In this thesis, we present improved polyno-mial time combinatorial algorithms to solve this problem on star graphs.Under the Hamming distance, the shortest path improvement problem isstrongly NP-hard, and even if the network is a chain network, it is still NP-hard. In this thesis, we give linear time combinatorial algorithms to solvethis problem on star graphs. Under the l∞norm, there are polynomial-timealgorithms for solving the shortest path improvement problem on generalnetworks. We propose the improved algorithms to solve this problem ontrees and star graphs, and we show that the complexities of the algorithmsare also reduced. In this thesis, we mainly study the algorithms and com-plexities of the following four kinds of problems:Firstly, westudytheshortestpathimprovementproblemonstargraphsunder l1norm. We consider three different kinds of vertex pairs,whichare the vertex pairs from the center vertex to all other vertices, the vertexpairs from a given non-center vertex to all other non-center vertices and the vertexpairsfromagivennon-centervertextoallothervertices. Forthefirstvertex pair case, a linear time algorithm can be obtained. For the latter twovertex pair cases, we separately present the polynomial time combinatorialalgorithms. finally we give the instances of this problem.Secondly, we consider the shortest path improvement problem on s-tar graphs under the Hamming distance. we consider two different vertexpairs, which are the vertex pairs from a given non-center vertex to all oth-er non-center vertices and the vertex pairs from a given non-center vertexto all other vertices. We separately obtain the linear time combinatorialalgorithms.Thirdly, we research the shortest path improvement problem form agiven vertex to all other vertices on the trees under l∞norm. Since thereare polynomial time algorithms on general graphs, we discuss the problemwith the costs and without the costs on trees. And we obtain improvedalgorithms with time complexity O(|V|2).Fourthly, we discuss the shortest path improvement problem from agivennon-centervertextoallothernon-centerverticesonstargraphsunderl∞norm. We further improve the algorithm on trees, then we obtain theimproved polynomial algorithm on star graphs, and the time complexity ofthe algorithm is O(n2), in which n=|V|2and|V|is the number of thevertices on the star graph.