Constructing Eulerian Trails in a Graph: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 32: | Line 32: | ||
[[File:Constructing Eulerian Trails in a Graph - Space.png|1000px]] | [[File:Constructing Eulerian Trails in a Graph - Space.png|1000px]] | ||
== | == Space-Time Tradeoff Improvements == | ||
[[File:Constructing Eulerian Trails in a Graph - Pareto Frontier.png|1000px]] | [[File:Constructing Eulerian Trails in a Graph - Pareto Frontier.png|1000px]] | ||
Revision as of 14:36, 15 February 2023
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
No parameters found.
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)$ loglogE) | $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
Space-Time Tradeoff Improvements
Error creating thumbnail: Unable to save thumbnail to destination