#9910: Longest path
----------------------------------------------+-----------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: positive_review
Priority: major | Milestone: sage-4.6.2
Component: graph theory | Keywords:
Author: Nathann Cohen | Upstream: N/A
Reviewer: Robert Miller, Minh Van Nguyen | Merged:
Work_issues: |
----------------------------------------------+-----------------------------
Comment(by pang):
This is a comment from an outsider, so it may not make much sense: you
mention in the docstring that this problem is NP-hard, and I agree there
doesn't seem to be an algorithm that is polinomial in the number of edges,
but:
In the paper
http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf
there is an algorithm to list all elementary circuits in a graph that is
linear in the number of circuits. This algorithm is implemented in version
1.4 of networkx:
https://networkx.lanl.gov/trac/ticket/394
Is the situation for paths instead of circuits much different? Is a MILP
algorithm better than listing all elementary paths by a Johnson-like
algorithm and finding the max lenght? Maybe MILP is better in practice but
is it in theory?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9910#comment:13>
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.
