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

Jump to navigation
Jump to search

## 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 |