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

$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