Algorithm Space/Time Complexity

This page aggregates space and time complexities for the various algorithms implemented in igraph. This page serves to be a quick view of the algorithms.

Algorithm R function name Space Time
Shortest Path Dijkstra shortest.paths() O(V^2) O(s*|E|log|E|+|V|)
Shortest Path Bellman Ford shortest.paths() O(V^2) O(s*|E|*|V|)
Shortest Path (Unweighted) shortest.paths() O(V^2) O(n(|V|+|E|))
Alpha Centrality alpha.centrality() O(V^2) ?
Decompose decompose.graph() ? O(|V|+|E|)
Average Path Length average.path.length() ? O(|V|*|E|)
Diameter diameter() ? O(|V|*|E|)
Girth girth() ? O((|V|+|E|)^2)
Closeness Centrality closeness() O(V) O(n|E|)
Betweenness Centrality betweenness() O(V) O(|V|*|E|)
Edge Betweenness edge.betweenness() O(V) O(|V|*|E|)
Eigenvector Centrality evcent() O(V) O(|V|)
Hub Score (Kleinberg) hub.score() O(V) O(|V|)
Authority Score (Kleinberg) authority.score() O(V) O(|V|)

s: the number of sources
n: the number of vertices to calculate
V: the number of vertices in the graph
E: the number of edges in the graph

page revision: 1, last edited: 10 Feb 2009 19:41