id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
27540 Approximate Algorithm for Diameter of graph gh-Hrishabh-yadav "Currently sage implements Multisweep algorithm with iFUB to find Diameter of undirected unweighted graph, whose complexity in worst case is O(M*N) M=Number of edges, N=Number of vertices. I came across this paper :-
https://epubs.siam.org/doi/pdf/10.1137/S0097539796303421 which implements approximate algorithm for diameter for both (un)weighted and (un)directed graph.
This algorithm develops the estimate of E, where (2/3)*∆ ≤ E ≤ ∆ . ∆ being diameter of graph. This algorithm works 5 times faster than other approximations, As there are no current algorithm for diameter of weighted graph which doesn't use All pair shortest path(ASAP) algorithm, This algorithm might be quite useful for finding diameter of large sparse graphs. " enhancement new major graph theory dcoudert N/A