[Networkit] new diameter algorithm - benchmark

Henning Meyerhenke henning.meyerhenke at kit.edu
Tue Feb 16 16:51:51 CET 2016



Am 16.02.16 um 16:17 schrieb Christian Staudt:
> 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.

Please retain iFub for comparison (and teaching) purposes. If SumSweep
is clearly better in all possible scenarios, then it is certainly okay
to mark iFub as retired.

Thanks,
Henning



> 
> Chris
> 
> 
> [1]: http://www.sciencedirect.com/science/article/pii/S0304397512008687
> [2]: http://link.springer.com/chapter/10.1007/978-3-319-07890-8_5
> 
> 
> 
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
> 

-- 

==========================================================
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)

Prof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing

Phone: +49-721-608-41876
Web: http://parco.iti.kit.edu/henningm/

KIT - The Research University in the Helmholtz Association
==========================================================

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5399 bytes
Desc: S/MIME Cryptographic Signature
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20160216/7b9ee723/attachment.p7s>


More information about the NetworKit mailing list