Constructing Eulerian Trails in a Graph (Constructing Eulerian Trails in a Graph)
Revision as of 10:21, 15 February 2023 by Admin (talk | contribs) (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...")
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
Pareto Decades graph
Error creating thumbnail: Unable to save thumbnail to destination