Editing Eulerian path (section)

=== Fleury's algorithm ===
'''Fleury's algorithm''' is an elegant but inefficient algorithm that dates to 1883.<ref>{{citation|first=Pierre-Henry<!-- See https://hsm.stackexchange.com/questions/12633/who-was-fleury-and-what-was-his-first-name -- in the publication, the "M." in "M. Fleury" is just short for monsieur, and should not be listed as Fleury's first initial -->|last=Fleury|title=Deux problèmes de Géométrie de situation|language=fr|url=https://books.google.com/books?id=l-03AAAAMAAJ&pg=PA257|journal=Journal de mathématiques élémentaires|series=2nd ser.|volume=2|year=1883|pages=257–261}}.</ref> Consider a graph known to have all edges in the same component and at most two vertices of odd degree. The algorithm starts at a vertex of odd degree, or, if the graph has none, it starts with an arbitrarily chosen vertex. At each step it chooses the next edge in the path to be one whose deletion would not disconnect the graph, unless there is no such edge, in which case it picks the remaining edge left at the current vertex. It then moves to the other endpoint of that edge and deletes the edge. At the end of the algorithm there are no edges left, and the sequence from which the edges were chosen forms an Eulerian cycle if the graph has no vertices of odd degree, or an Eulerian trail if there are exactly two vertices of odd degree.

While the ''graph traversal'' in Fleury's algorithm is linear in the number of edges, i.e. <math>O(|E|)</math>, we also need to factor in the complexity of detecting [[Bridge (graph theory)|bridge]]s. If we are to re-run [[Robert Tarjan|Tarjan]]'s linear time [[Bridge (graph theory)#Tarjan's bridge-finding algorithm|bridge-finding algorithm]]<ref>{{citation
 | last = Tarjan | first = R. Endre | author-link = Robert Tarjan
 | doi = 10.1016/0020-0190(74)90003-9
 | year = 1974
 | issue = 6
 | journal = Information Processing Letters
 | mr = 0349483
 | pages = 160–161
 | title = A note on finding the bridges of a graph
 | volume = 2}}.</ref> after the removal of every edge,  Fleury's algorithm will have a time complexity of <math>O(|E|^2)</math>. A dynamic bridge-finding algorithm of {{harvtxt|Thorup|2000}} allows this to be improved to <math>O(|E| \cdot \log^3 |E| \cdot \log \log |E|)</math>, but this is still significantly slower than alternative algorithms.