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