Friday, 16 October 2009

Good algorithm for finding the diameter of a (sparse) graph?

In general it does not seem that the diameter computation implies APSP.
Indeed If the graph is undirected the following can be applied.



Pilu Crescenzi, Roberto Grossi, Michel Habib, Leonardo Lanzi, Andrea Marino: On computing the diameter of real-world undirected graphs. TCS 2012.



and if the graph is directed the following can be applied.



Pierluigi Crescenzi, Roberto Grossi, Leonardo Lanzi, Andrea Marino: On Computing the Diameter of Real-World Directed (Weighted) Graphs. SEA 2012.



In the worst case the complexity of these methods is the same as computing APSP, but in real world cases it has been experimentally shown that they run in O(m), where m is the number of edges. Both can be used even if the graph is weighted.



Regards



Andrea Marino

No comments:

Post a Comment