Menu
Could you please help me find out the time complexity of the Fleury' algorithm (which is used to get the Eulerian circuit)?
650
Fleury's Algorithm is used to display the Euler path or Euler circuit from a given graph. In this algorithm, starting from one edge, it tries to move other adjacent vertices by removing the previous vertices. Using this trick, the graph becomes simpler in each step to find the Euler path or circuit.
FLEURY'S ALGORITHM If Euler's Theorem indicates the existence of an Euler path or Euler circuit, one can be found using the following procedure: If the graph has exactly two odd vertices choose one of these odd vertices as the starting point of an Euler path. If the graph has no odd vertices it has an Euler circuit.
If there are 0 odd vertices, start anywhere. If there are 2 odd vertices, start at one of them.
Fleury's Algorithm shows us how to find Euler Circuits and Euler Paths, but only on graphs where all vertices are of even degree, or if there are only two vertices of odd degree.
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 :))
82
Here: http://roticv.rantx.com/book/Eulerianpathandcircuit.pdf you can read among other things, that it is O(E), linear edge count.
30
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
