Research On The Maximum Bandwidth Path Problem Of All Node Pairs

Bandwidth is an important indicator to measure the data transmission capability of signal transmission,which identifies the amount of data passing through the link per unit time.However,existing bandwidth resources are limited,so it is necessary to seek a maximum bandwidth path during network transmission.In the current network environment,data transmission events occur frequently,and we are faced with the great challenge of how to quickly respond to the maximum bandwidth path required for data transmission.Finding the maximum bandwidth path of all node pairs in advance can quickly provide the required maximum bandwidth path when a data transmission event occurs between any two network nodes,thereby improving network transmission performance.Therefore,it is of great theoretical and practical value to study the algorithm of the maximum bandwidth path problem for all node pairs.The main content of this thesis is as follows:(1)A maximum bandwidth path algorithm for all node pairs is proposed,which can be used directly on disconnected graphs,by proving that its time complexity is(9)9)~2)and space complexity is(9)9)~2)(where9)9)is the number of nodes in the graph),in order to directly solve the optimal time complexity and space complexity of all nodes to the maximum bandwidth path,and to query the bandwidth value of the maximum bandwidth path of any node pair in(1)time,is the optimal query time for the bandwidth value of the maximum bandwidth path.(2)Based on the optimal minimum spanning tree algorithm proposed by Seth Pettie and Vijaya Ramachandran,a maximum spanning forest algorithm is designed.It is proved that its time complexity is(*(8)8),9)9))),and its space complexity is(*(8)8),9)9))),is the optimal maximum spanning forest algorithm,where*is the number of comparisons of the maximum edge weight required to determine the solution,8)8)is the number of edges in the graph,9)9)is the number of nodes in the graph,Running in graphs is linear time with high probability.(3)Based on the property of the least common ancestor in the forest,a maximum bandwidth path query algorithm for any node pair is proposed.It is proved that the time complexity of the algorithm preprocessing is O(*(8)8),9)9)))and the space complexity is O(*(8)8),9)9))),the query time is(6)6))(where6)6)is the number of nodes passed by two points,which is the optimal path query time).Based on the property of the node hierarchy in the maximum spanning forest,the maximum bandwidth path query algorithm for any node pair is optimized.Compared with the original algorithm,although the preprocessing time space complexity is the same as the query time,the optimized algorithm is simpler.Intuitive,flexible,and easier to implement.