Classical eulerian cycle algorithm: Difference between revisions
(→Remark) |
|||
| Line 15: | Line 15: | ||
== Complexity == | == Complexity == | ||
'''Statement:''' | |||
oth for directed and undirected graphs, the asymtptotic complexity is <math>\mathcal{O}(n+m)</math>, where <math>n</math> is the number of nodes and <math>m</math> the number of edges/ars. | |||
'''Proof:''' | |||
== Remark == | == Remark == | ||
Of course, the edges/arcs need not be removed permanently. However, when an edge/arc is processed, it must be hidden from the algorithm up to its termination to achieve the linear bound on the complexity. | Of course, the edges/arcs need not be removed permanently. However, when an edge/arc is processed, it must be hidden from the algorithm up to its termination to achieve the linear bound on the complexity. | ||
Revision as of 09:06, 12 October 2014
General information
Algorithmic problem: Eulerian cycle
Type of algorithm: recursion with an arbitrarily chosen start node as an additional input.
Induction basis
Abstract view: The output sequence [math]\displaystyle{ S }[/math] of nodes and arcs is initialized so as to contain the start node [math]\displaystyle{ s }[/math] and nothing else.
Induction step
If the start node has
Complexity
Statement: oth for directed and undirected graphs, the asymtptotic complexity is [math]\displaystyle{ \mathcal{O}(n+m) }[/math], where [math]\displaystyle{ n }[/math] is the number of nodes and [math]\displaystyle{ m }[/math] the number of edges/ars.
Proof:
Remark
Of course, the edges/arcs need not be removed permanently. However, when an edge/arc is processed, it must be hidden from the algorithm up to its termination to achieve the linear bound on the complexity.