Fleury's time complexity

Question

Could you help me find out the temporal complexity of the Fleury algorithm (which is used to obtain the Eulerian scheme)?

Answer 1

Here: http://roticv.rantx.com/book/Eulerianpathandcircuit.pdf you can read by the way that this is O (E), the number of linear boundaries.

Answer 2

The Fleury algorithm is not actually populated until you indicate how the edges of the bridge are identified. Tarjan gave a linear time algorithm for identifying all bridges (see http://en.wikipedia.org/wiki/Bridge_(graph_theory) ), so the naive implementation that repeated the Tarjan algorithm after each remote edge is O (E ^ 2). There are probably better ways to rearrange the bridge set, 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

The Fleury algorithm includes the following steps:

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

• If there are 0 odd vertices, start anywhere. If there are two odd vertices, start with one of them.

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

• Stop when you finish the edges.

If Tarjan bridges are found, and these bridges are stored in the adjacency matrix, we do not need to run the tarjan algorithm each time to check if the edge is a bridge or not. We can check it O (1) times for all other bridge requests. Thus, the time complexity of the Flury algorithm can be reduced to O (V + E) {, since it is DFS}, but this method O (V2) requires additional storage space for bridges.