What is the problem name for Traveling salesman problem(TSP) without considering going back to starting point?

by

I’ve found the answer to my question in this book. It is the same with Computer wiring problem which occurs repeatedly in the design of computers and other digital systems. The purpose is to minimize the total wire length. So, it is indeed a minimum length Hamiltonian path.

What the book suggests is to create a dummy point whose distances to every other points is 0. Therefore, the problem becomes an (n+1)-city symmetric TSP. After solving, just delete dummy point and then the minimum length Hamiltonian path is solved and we can get the TSP path without returning back the start point.

More Related Contents:

  1. Finding all cycles in a directed graph
  2. Negative weights using Dijkstra’s Algorithm
  3. Travelling Salesman with multiple salesmen?
  4. 3 dimensional bin packing algorithms
  5. What are the differences between segment trees, interval trees, binary indexed trees and range trees?
  6. Why does Dijkstra’s algorithm use decrease-key?
  7. Why is depth-first search claimed to be space efficient?
  8. Algorithm to simplify a weighted directed graph of debts
  9. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  10. Fastest sort of fixed length 6 int array
  11. What is the best way to get the minimum or maximum value from an Array of numbers?
  12. How does one convert 16-bit RGB565 to 24-bit RGB888?
  13. Sign of a symbolic algebraic expression
  14. Shortest path to transform one word into another
  15. How does lucene index documents?
  16. How to efficiently calculate a row in pascal’s triangle?
  17. A Good and SIMPLE Measure of Randomness
  18. What is the best way to check the strength of a password?
  19. Algorithm for merging two max heaps?
  20. What is the best algorithm for finding the closest color in an array to another color? [closed]
  21. Compute the area of intersection between a circle and a triangle?
  22. Unbiased random number generator using a biased one
  23. Why is vector array doubled?
  24. maximum subarray of an array with integers [duplicate]
  25. Quadratic algorithm for 4-SUM
  26. CUDA stream compaction algorithm
  27. Can brute force algorithms scale?
  28. What is the algorithm that opencv uses for finding contours?
  29. Find XOR of all numbers in a given range
  30. Best algorithm for matching colours.

Leave a Comment