Constructing Eulerian Trails in a Graph (Constructing Eulerian Trails in a Graph)

From Algorithm Wiki
Jump to navigation Jump to search


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.


$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

Constructing Eulerian Trails in a Graph - Time.png