#9698: Hamiltonian cycles in undirected graphs - backtracking algorithm.
----------------------------------+-----------------------------------------
Reporter: fidelbarrera | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-4.5.3
Component: graph theory | Keywords:
Author: Fidel Barrera-Cruz | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------------+-----------------------------------------
Changes (by ncohen):
* status: needs_review => needs_info
Comment:
Wow !!! This sounds great !! I promise I will give this patch a look as
soon as possible ! :-)
I have a few questions already...
* I noticed you mentionned in the doc that the backtrack algorithm may
not return an optimal hamiltonian path, but don't you think it may be
better to create another function for it, rather than having a method
whose answer may be exact or not depending on the algorithm used ?
* If your algorithm is fast enough, could it be interesting to check when
calling is_hamiltonian the answer given by your algorithm before solving
the actual tsp problem (which is sometimes veeeeeery long) ?
* Main question : as it is a backtracking algorithm, and this may require
a lot of computational work... What would you think of making it a Cython
function, to give t more energy ? :-)
Thaaaanksssssssss ! :-)
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9698#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
