Material Detail

Approximating TSP Solution by MST based Graph Pyramid

Approximating TSP Solution by MST based Graph Pyramid

This video was recorded at 6th IAPR - TC-15 Workshop on Graph-based Representations in Pattern Recognition (GbR), Alicante 2007. The traveling salesperson problem (TSP) is difficult to solve for input instances with large number of cities. Instead of finding the solution of an input with a large number of cities, the problem is approximated into a simpler form containing smaller number of cities, which is then solved optimally. Graph pyramid solution strategies, in a bottom-up manner using Boruvka's minimum spanning tree, convert a 2D Euclidean TSP problem with a large number of cities into successively smaller problems (graphs) with similar layout and solution, until the number of cities is small enough to seek the optimal solution. Expanding this tour solution in a top-down manner to the... Show More
Rate

Quality

  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material

Browse...

Disciplines with similar materials as Approximating TSP Solution by MST based Graph Pyramid

Comments

Log in to participate in the discussions or sign up if you are not already a MERLOT member.
hidden