A minimal spanning path in a graph is a path that contains all the vertices of a graph whose weight is the least among the spanning paths.
This is a question much related to finding a Hamiltonian path - where a Hamiltonian cycle would be a feasible solution to the famous traveling salesperson problem. The current standing on the Hamiltonian path question is that it is unknown whether it is hard or not - no-one has yet found a polynomial algorithm for the problem.
I agree with Prof. Michael Patriksson. A reliable algorithm for finding a Hamilton cycle/path in a graph is unknown so far. The following links may help you a bit in this regard.
ftp://www.combinatorialmath.ca/g&g/chalaturnykthesis.pdf
http://link.springer.com/article/10.1007%2FBF02579321
Finding minimal spanning path is essentially finding a degree constrained minimal spanning tree (the constraint on degree d in your case is that d is less or equal to 2. This constraint makes it a hamiltonian path. Both these problems, i.e. the problem of finding degree constrained minimal tree or shortest hamiltonian path are NP Complete problems and have no known polynomial time solution.
You may find following link interesting and useful.
https://www.researchgate.net/publication/267377360_Polynomial_Algorithms_for_Shortest_Hamiltonian_Path_and_Circuit
Article Polynomial Algorithms for Shortest Hamiltonian Path and Circuit
- Badges
- Science topic
- Similar topics
- Mathematics