Vertex tour in a weighted undirected graph with the maximum cost?

What are the efficient algorithms for finding a vertex tour in a weighted undirec开发者_StackOverflow社区ted graph with maximum cost if we need to start from a particular vertex?

---

It's NPC because if you set weights as 1 for all edges, if HC exists it will be your answer, and so In all you can find HC existence from a single source which is NPC by solving this problem so your problem is NPC, but there are some polynomial approximation algorithms.

---

Since the problem is NP-hard, you are very unlikely to find an efficient algorithm that solves the problem exactly for all possible weighted input graphs.

However, there might be efficient algorithms that are guaranteed to find an answer that is at most a constant times away from the best possible answer, e.g. there might be an efficient algorithm that is guaranteed to find a path that has weight at least 1/2 of the maximum weight path.

If you are interested in searching for such algorithms, you could try Google searches for "weighted hamiltonian path approximation algorithm", which is close to, but not identical to, your problem. It is not the same because Hamiltonian paths are required to include all vertexes. Here is one research paper that might either contain, or have ideas that lead to, an approximation algorithm for your problem:

http://portal.acm.org/citation.cfm?id=139404.139468

"A general approximation technique for constrained forest problems" by Michel X. Goemans and David P. Williams.

Of course, if your graphs are small enough that you can enumerate all possible paths containing your desired vertex "fast enough for your purposes", then you can solve it exactly.