Constructing Eulerian Trails in a Graph: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| 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] | ||
|- | |- | ||
|} | |} | ||
| Line 27: | Line 29: | ||
[[File:Constructing Eulerian Trails in a Graph - Time.png|1000px]] | [[File:Constructing Eulerian Trails in a Graph - Time.png|1000px]] | ||
Latest revision as of 09:08, 28 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
