[Networkit] Getting pair of nodes with shortest path distance equal to the diameter?

Michael Hamann michael.hamann at kit.edu
Thu Dec 15 14:50:50 CET 2016


Hi all,

On 15.12.2016 12:39, Matteo Riondato wrote:
> After having computed the diameter or run APSP, is there an easy what to get the pair of nodes whose shortest path distance is equal to the diameter of the graph (or a vector of the pairs or any pair, if there are multiple pairs ) ?

Computing the diameter is not necessarily an APSP computation. The 
algorithm we have currently implemented only for unweighted, undirected 
graphs [0] uses a lot of different bounds. Probably, one can find and 
keep track of node pairs for the bounds and report the matching one at 
the end. If not, one can definitely at least get a node with maximum 
eccentricity and run another BFS from it to get the other node.

For all other exact variants we have an APSP implementation where 
getting such a node pair is trivial to implement but currently not 
implemented.

Best,
Michael

[0]: http://dx.doi.org/10.1016/j.tcs.2015.02.033



More information about the NetworKit mailing list