search

JuliaGraphs / Graphs.jl

An optimized graphs package for the Julia programming language
http://juliagraphs.org/Graphs.jl/
Other
451 stars 87 forks source link

dorogovtsev_mendes graph generator is running in O(n^2) #370

Closed AntoineBut closed 2 months ago

AntoineBut commented 3 months ago

Generating a graph of size N using the dorogovtsev_mendes algorithm should run in $O(N)$ and not $O(N^2)$. (see source)

I actually don't really understand why this has been implemented this way, and I can try to make a more efficient implementation.

gdalle commented 3 months ago

that would be a welcome contribution, thanks!