1
$\begingroup$

How to improve the worst case scenario for a depth first search on an Euler graph, starting at some point and ending at that same point?

I need to do the whole search but it is not fast enough for large amounts of data. I have tried bidirectional search but I can not keep the result numerically ordered. Therefore I wonder if there is any other good method to smooth the worst case scenario for the depth first search.

Improve this question
$\endgroup$
12
  • 4
    $\begingroup$ What is the goal here, finding an euler path? Why do you "need to do the whole search"? What does "numerically ordered" mean here? $\endgroup$
    – Raphael ♦
    Mar 21, 2012 at 16:14
  • 3
    $\begingroup$ Why do you care if it's numerically ordered ? it might not even be feasible if that's a requirement. $\endgroup$
    – Suresh
    Mar 21, 2012 at 16:44
  • 1
    $\begingroup$ Have you tried Wikipedia? $\endgroup$
    – Raphael ♦
    Mar 21, 2012 at 16:50
  • 1
    $\begingroup$ Maybe I don't understand what numerically ordered means. If you have a cycle on 4 vertices, where they are numbered 1-3-2-4-1, then there's a Euler tour but not one that's numerically ordered. $\endgroup$
    – Suresh
    Mar 21, 2012 at 17:28
  • 7
    $\begingroup$ Even after reading the comment thread, I don't understand what you mean by “numerically ordered”. Please edit your question to explain (preferably with some well-chosen examples). $\endgroup$
    – Gilles 'SO- stop being evil'
    Mar 21, 2012 at 22:11

1 Answer 1

Reset to default
3
$\begingroup$

If I understand correctly, the only way to have a numerically ordered eulerian path would be having a path looking like 1,2,3..,n,1. All nodes in the path must have degree 2 (since you can only get into the once), except perhaps for nodes with degree 0, that you can instead skip.

If this is the case, the algorithm would just be a matter of testing if the 1,2,3..n path is eulerian, with no need to find eulerian paths with a traditional algorithm.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.