Constructing Eulerian Trails in a Graph (Constructing Eulerian Trails in a Graph)
Jump to navigation
Jump to search
Description
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex.
Parameters
$V$: number of vertices
$E$: number of edges
Table of Algorithms
Name | Year | Time | Space | Approximation Factor | Model | Reference |
---|---|---|---|---|---|---|
Fleury's algorithm + Tarjan | 1974 | $O(E^{2})$ | $O(E)$ | Exact | Deterministic | Time |
Hierholzer's algorithm | 1873 | $O(E)$ | $O(E)$ | Exact | Deterministic | |
Fleury's algorithm + Thorup | 2000 | $O(E \log^{3}(E)$ \log\log E) | $O(E)$ | Exact | Deterministic | Time |
Time Complexity Graph
Error creating thumbnail: Unable to save thumbnail to destination
Space Complexity Graph
Error creating thumbnail: Unable to save thumbnail to destination
Time-Space Tradeoff
Error creating thumbnail: Unable to save thumbnail to destination