Sage: Ticket #27540: Approximate Algorithm for Diameter of graph
https://trac.sagemath.org/ticket/27540
<p>
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 :-
<a class="ext-link" href="https://epubs.siam.org/doi/pdf/10.1137/S0097539796303421"><span class="icon"></span>https://epubs.siam.org/doi/pdf/10.1137/S0097539796303421</a> which implements approximate algorithm for diameter for both (un)weighted and (un)directed graph.
</p>
<p>
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.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/27540
Trac 1.1.6dcoudertSat, 23 Mar 2019 18:37:00 GMT
https://trac.sagemath.org/ticket/27540#comment:1
https://trac.sagemath.org/ticket/27540#comment:1
<p>
A significant research effort has been done since 2009 (the paper you cite is from 1999) to design fast exact algorithms for the diameter of (un)weighted (directed) graphs. So why not implementing the weighted version of iFUB instead of an approximation ?
</p>
Ticketgh-Hrishabh-yadavSat, 23 Mar 2019 19:29:31 GMT
https://trac.sagemath.org/ticket/27540#comment:2
https://trac.sagemath.org/ticket/27540#comment:2
<p>
Most of the paper have generalised the same multisweep algorithm with Dijikstra instead BFS. None of them haven't actually written much about it. Do have any good research paper explaining complexity of iFUB with dijikstra. Thanks:)
</p>
Ticketgh-Hrishabh-yadavSun, 24 Mar 2019 08:55:01 GMT
https://trac.sagemath.org/ticket/27540#comment:3
https://trac.sagemath.org/ticket/27540#comment:3
<p>
This paper:- <a class="ext-link" href="http://pages.di.unipi.it/marino/diameter.pdf"><span class="icon"></span>http://pages.di.unipi.it/marino/diameter.pdf</a> shows us that we can find diameter of directed graph using DiFUB. This paper also suggested for weighted graphs we can use Dijikstra instead of BFS. So complexity for weighted graphs in worst case should be O(N*M*Log(N)), but similarly like unweighted graphs(O(M)), average complexity of weighted will be O(M*log(n)), which will far better for sparse graphs than any other algorithm.
</p>
TicketdcoudertSun, 24 Mar 2019 14:44:39 GMT
https://trac.sagemath.org/ticket/27540#comment:4
https://trac.sagemath.org/ticket/27540#comment:4
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/27540#comment:3" title="Comment 3">gh-Hrishabh-yadav</a>:
</p>
<blockquote class="citation">
<p>
This paper:- <a class="ext-link" href="http://pages.di.unipi.it/marino/diameter.pdf"><span class="icon"></span>http://pages.di.unipi.it/marino/diameter.pdf</a> shows us that we can find diameter of directed graph using DiFUB. This paper also suggested for weighted graphs we can use Dijikstra instead of BFS.
</p>
</blockquote>
<p>
The complexity of all these exact algorithms is O(n * SSSP), where SSSP is the time complexity for single source shortest-path tree. In general in the paper they use BFS instead of Dijkstra to ease the presentation, but they all say (including in the iFUB paper) that you can replace BFS by Dijkstra.
</p>
<blockquote class="citation">
<p>
So complexity for weighted graphs in worst case should be O(N*M*Log(N)), but similarly like unweighted graphs(O(M)), average complexity of weighted will be O(M*log(n)), which will far better for sparse graphs than any other algorithm.
</p>
</blockquote>
<p>
I don't know where you found an average time complexity proof for iFUB/DiFUB in (un)weighted graphs. I'm not aware of any such proof.
</p>
<p>
The (currently) best theoretical explanation of the good performances of such algorithms is in <a class="ext-link" href="http://arxiv.org/abs/1803.04660"><span class="icon"></span>http://arxiv.org/abs/1803.04660</a>.
</p>
TicketembrayFri, 14 Jun 2019 14:55:02 GMTmilestone deleted
https://trac.sagemath.org/ticket/27540#comment:5
https://trac.sagemath.org/ticket/27540#comment:5
<ul>
<li><strong>milestone</strong>
<em>sage-8.8</em> deleted
</li>
</ul>
<p>
As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).
</p>
Ticket