Hi all could you please help me find out the time complexity of the Fleury' algoritm(which is used to get the Eulerian circuit)? Searched on the web,but no results.
thanks/
+2
A:
Here: http://roticv.rantx.com/book/Eulerianpathandcircuit.pdf you can read among other things, that it is O(E), linear edge count.
Gabriel Ščerbák
2010-03-09 00:33:31
It attributes the algorithm in my second link to Fleury, which is not supported by any other source I can find.
2010-03-09 00:53:27
I am not familiar with that algorithm or that particular paper, so I cannot tell.
Gabriel Ščerbák
2010-03-09 01:30:40
+5
A:
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 :))