search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.43k stars 478 forks source link

Approximate Algorithm for Diameter of graph #27540

Open a396f486-5fc5-40c2-a542-2e12efb37784 opened 5 years ago

a396f486-5fc5-40c2-a542-2e12efb37784 commented 5 years ago

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.

CC: @dcoudert

Component: graph theory

Issue created by migration from https://trac.sagemath.org/ticket/27540

dcoudert commented 5 years ago
comment:1

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 ?

a396f486-5fc5-40c2-a542-2e12efb37784 commented 5 years ago
comment:2

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:)

a396f486-5fc5-40c2-a542-2e12efb37784 commented 5 years ago
comment:3

This paper:- http://pages.di.unipi.it/marino/diameter.pdf 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(NMLog(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.

dcoudert commented 5 years ago
comment:4

Replying to @Hrishabh-yadav:

This paper:- http://pages.di.unipi.it/marino/diameter.pdf 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.

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.

So complexity for weighted graphs in worst case should be O(NMLog(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.

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.

The (currently) best theoretical explanation of the good performances of such algorithms is in http://arxiv.org/abs/1803.04660.

embray commented 5 years ago
comment:5

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).