Local Reconstruction Of Fault Path And Design Of Approximate Algorithm Of Dynamic Restricted Shortest Path In Network

In communication network,the construction,repair and optimization of path are always the key problems in network.In the process of wireless communication network operation there will be a variety of fault problems or need to consider the cost and energy consumption tradeoff issues,this paper wireless network in the local fault repair and dynamic limit the shortest circuit problem to carry out research.In order to restore the faulty path in network more effectively,we propose the maintaining constrained path problem.Given a directed acyclic graph(DAG)G=(V(G),E(G))with some faulty edges,where |V(G)|=n,|E(G)|=m.For any positive number D,we give effective maintain algorithm for finding and maintaining the path between source vertex s ∈ V(G)and destination t ∈ V(G)with length at most D.In this paper,we consider the parameters ||δ|| and |δ| which are used to measure the numbers of edges and vertices which are influenced by faulty edges,respectively.The main technique of this paper is to define and solve a subproblem called the one to set constrained path problem(OSCPP)which has not been addressed before.On the DAG,compared with the dynamic shortest path algorithm with time complexity O(||δ||+|δ| log |δ|)and the shortest path algorithm with time complexity O(m+n),based on the algorithm for OSCPP,we develop a maintaining constrained path algorithm and improve the time complexity to O(||δ||+|δ|)in the case that all shortest paths from each vertex u ∈ V(G)to t have been given.In time-dependent communication network,in order to improve work efficiency under the constraint of cost,we study the problem of minimizing the total time of the transmission path subject to an upper-bound of the total cost in a directed graph,where the cost between any two nodes changes as time due to the dynamic network conditions.The consideration of dynamic network conditions not only makes our study more practical but also allows us to save cost by utilizing the delay time.In this paper,by a given parameter,we firstly reset the transmission time function which will be used to construct the auxiliary graph.Then,according to the transmission path in auxiliary graph,we define the corresponding transmission process in original graph.Thus,we propose a(1+ε)-approximate algorithm in auxiliary graph to solve this problem with fully polynomial time complexity(?).