Topological Sorting: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 34: | Line 34: | ||
[[File:Topological Sorting - Space.png|1000px]] | [[File:Topological Sorting - Space.png|1000px]] | ||
== | == Space-Time Tradeoff Improvements == | ||
[[File:Topological Sorting - Pareto Frontier.png|1000px]] | [[File:Topological Sorting - Pareto Frontier.png|1000px]] | ||
Revision as of 14:36, 15 February 2023
Description
Given a graph or network, find a topological sorting of the graph. A list in topological order has a special property. Simply expressed: proceeding from element to element along any path in the network, one passes through the list in one direction only. Stated another way, a list in topological order is such that no element appears in it until after all elements appearing on all paths leading to the particular element have been listed.
Parameters
V: number of vertices
E: number of edges
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Kahn's algorithm | 1962 | $O(V+E)$ | $O(V)$ auxiliary | Exact | Deterministic | Time |
| Tarjan's DFS based algorithm | 1976 | $O(V+E)$ | $O(V)$ auxiliary? | Exact | Deterministic | Time |
| Dekel; Nassimi & Sahni Parallel Implementation | 1981 | $O( log² V)$ | $O(V^{2})$?? | Exact | Parallel | Time |
Time Complexity Graph
Space Complexity Graph
Space-Time Tradeoff Improvements
