[Networkit] new core decomposition algorithm

Christian Staudt christian.staudt at kit.edu
Wed Sep 16 18:58:14 CEST 2015

It seems to me that the new implementation of core decomposition is no improvement. I ran just a few tests on big graphs:

uk-2002 (260 M edges):
old: Wall time: 22.7 s
new: Wall time: 44 s

eu-2005 (54 M edges)
old: Wall time: 13.5 s
new: Wall time: 30.1 s

This is bad considering that old version is sequential and the new version ran in parallel with 32 threads. Anyone getting different results for large graphs (which are those that matter)?

I suggest reverting the changes in the Dev branch and testing the new algorithm in a separate branch, until experiments show that it is in general faster than the existing implementation.


ps. By the way, I consider the previous implementation more or less fast enough, so a better algorithm is not urgently needed in my opinion.

-------------- 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/20150916/68fa8772/attachment.sig>

More information about the NetworKit mailing list