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 |
||
| (4 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] | ||
|- | |- | ||
|} | |} | ||
== 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]] | ||
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
