Euler tour technique

Euler tour of a tree, with edges labeled to show the order in which they are traversed by the tour

The Euler tour technique (ETT), named after Leonhard Euler, is a method in graph theory for representing trees. The tree is viewed as a directed graph that contains two directed edges for each edge in the tree. The tree can then be represented as a Eulerian circuit of the directed graph, known as the Euler tour representation (ETR) of the tree. The ETT allows for efficient, parallel computation of solutions to common problems in algorithmic graph theory. It was introduced by Tarjan and Vishkin in 1984.[1]

  1. ^ Tarjan, R.E.; Vishkin, U. (1984). Finding biconnected components and computing tree functions in logarithmic parallel time. Proceedings of FOCS. pp. 12–20. CiteSeerX 10.1.1.419.3088. doi:10.1109/SFCS.1984q5896 (inactive 1 November 2024).{{cite conference}}: CS1 maint: DOI inactive as of November 2024 (link)