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.

$\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$ Mar 21, 2012 at 22:11

1 Answer 1

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.

$\endgroup$
0

Your Answer

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

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