[Networkit] new diameter algorithm - benchmark

Christian Staudt christian.staudt at kit.edu
Tue Feb 16 16:17:12 CET 2016


Michael replaced the diameter algorithm a while ago, here are some benchmark results:

old: iFub [1]


new: SumSweep






Result: For typical complex networks, they are basically equally fast. SumSweep just has much better worst-case behavior, which means it will also work on street-network like graphs.

SumSweep is what is called with distance.Diameter(G).run(), iFub is out.

Chris


[1]: http://www.sciencedirect.com/science/article/pii/S0304397512008687
[2]: http://link.springer.com/chapter/10.1007/978-3-319-07890-8_5

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20160216/3d36ea33/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screen Shot 2016-02-16 at 15.23.13.png
Type: image/png
Size: 40890 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20160216/3d36ea33/attachment-0002.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screen Shot 2016-02-16 at 16.07.54.png
Type: image/png
Size: 42541 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20160216/3d36ea33/attachment-0003.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20160216/3d36ea33/attachment-0001.sig>


More information about the NetworKit mailing list