A New Algorithm for Network Diameter

Network diameter is one of the important parameters of a network, until now, however, there has not been a perfect algorithm which has a lower time complexity than O(n²) to deal with this problem. As increasingly expanding of network scale and increasing number of nodes and edges, it would spend a lot of time that using Floyd algorithm whose time complexity is defined O(n³) or Breadth-first Search(BFS) algorithm whose time complexity is defined O(nm) to compute network diameter. Moreover, BFS is only effective in non-weighted graph. For decreasing the time complexity of computing network diameter, this paper proposes a novel algorithm, Compressing Graph(CG), which bases on the correlative knowledge of graph compression. Through the analysis of time complexity, it shows our algorithm is a feasible method applied for diverse topology graphs and its range of time complexity is O(n) to O(n³).