Constructing Eulerian Trails in a Graph: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
$V$: number of vertices | |||
$E$: number of edges | |||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 20: | Line 22: | ||
| [[Hierholzer's algorithm (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph)|Hierholzer's algorithm]] || 1873 || $O(E)$ || $O(E)$ || Exact || Deterministic || | | [[Hierholzer's algorithm (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph)|Hierholzer's algorithm]] || 1873 || $O(E)$ || $O(E)$ || Exact || Deterministic || | ||
|- | |- | ||
| [[Fleury's algorithm + Thorup (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph)|Fleury's algorithm + Thorup]] || 2000 || $O(E log^{3}(E)$ | | [[Fleury's algorithm + Thorup (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph)|Fleury's algorithm + Thorup]] || 2000 || $O(E \log^{3}(E)$ \log\log E) || $O(E)$ || Exact || Deterministic || [https://www.cs.princeton.edu/courses/archive/spr10/cos423/handouts/NearOpt.pdf Time] | ||
|- | |- | ||
|} | |} | ||
Revision as of 07:52, 10 April 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
$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
Space Complexity Graph
Time-Space Tradeoff
