Time complexity of Fleury's Algorithm

Question

Could you please help me find out the time complexity of the Fleury' algorithm (which is used to get the Eulerian circuit)?

Answer 1

Here: http://roticv.rantx.com/book/Eulerianpathandcircuit.pdf you can read among other things, that it is O(E), linear edge count.

Answer 2

Fleury's algorithm isn't really complete until you specify how the bridge edges are identified. Tarjan gave a linear-time algorithm for identifying all bridges (see http://en.wikipedia.org/wiki/Bridge_(graph_theory) ), so a naive implementation that reran Tarjan's algorithm after each deleted edge would be O(E^2). There are probably better ways to recompute the set of bridges, but there is also a better O(E) algorithm. (See http://www.algorithmist.com/index.php/Euler_tour#Fleury.27s_algorithm ; not my site :))

Answer 3

Fleury algorithm involves following steps :

1. Make sure the graph has either 0 or 2 odd vertices.

2. If there are 0 odd vertices, start anywhere. If there are 2 odd vertices, start at one of them.

3. Follow edges one at a time. If you have a choice between a bridge and a non-bridge, always choose the non-bridge.

4. Stop when you run out of edges.

If bridges are found out by Tarjan's algorithm and these bridges are stored in an adjacency matrix then we need not run tarjan's algorithm every time to check whether an edge is a bridge or not. We can check it in O(1) time for all other bridge queries. Thus Flury's algorithm time complexity can be reduced to O(V+E) {as this is a DFS} but this method needs O(V2) extra space to store bridges.