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