Constructing Eulerian Trails in a Graph: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Constructing Eulerian Trails in a Graph (Constructing Eulerian Trails in a Graph)}} == 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 == {| class="wikitable...") |
No edit summary |
||
| Line 24: | Line 24: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Constructing Eulerian Trails in a Graph - Time.png|1000px]] | [[File:Constructing Eulerian Trails in a Graph - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:Constructing Eulerian Trails in a Graph - Space.png|1000px]] | [[File:Constructing Eulerian Trails in a Graph - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[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:04, 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
Space Complexity Graph
Pareto Frontier Improvements Graph
