7
$\begingroup$

The Hamiltonian Cycle Problem and Travelling Salesman Problem are among famous NP-complete problems and has been studied extensively.

I am looking for applications of the HamCycle and TSP. What are some interesting real world problems where the HamCycle and TSP come up?

$\endgroup$
1
  • 3
    $\begingroup$ Few years ago, it was useful in genome sequencing. $\endgroup$
    – Saeed
    Jul 1, 2016 at 22:59

4 Answers 4

8
$\begingroup$

One application involves stripification of triangle meshes in computer graphics — a Hamiltonian path through the dual graph of the mesh (a graph with a vertex per triangle and an edge when two triangles share an edge) can be a helpful way to organize data and reduce communication costs.

$\endgroup$
7
$\begingroup$

Abstract: Multi-threshold CMOS (MTCMOS) is currently the most popular methodology in industry for implementing a power gating design, which can effectively reduce the leakage power by turning off inactive circuit domains. However, large peak current may be consumed in a power-gated domain during its sleep-to-active mode transition. As a result, major IC foundries recommend turning on power switches one by one to reduce the peak current during the mode transition, which requires a Hamiltonian-cycle routing to serially connect all the power switches. ...

  • Another """application""" (note the triple quotes :-) is puzzle games ... for example in the game RoundTrip (a.k.a. GrandTour) you must find an Hamiltonian circuit in a grid of points in which some of the edges are given.

enter image description here

But there are many other puzzles/videogames that are directly inspired by the Hamiltonian circuit/path problem: Inertia, Pearl, Rolling Cube Puzzles, Slither,...

... and the "hardness" of HC makes them addictive: even small instances can be very hard to solve for our brain!!!

$\endgroup$
5
$\begingroup$

(Variants of the) TSP show(s) up routinely in several routing and scheduling problems (think of the route planned for a UPS truck out of delivering packages, for instance). But a great place to learn about several applications of the TSP is Chapter 3 of the book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation by Bill Cook. In particular, he talks about mapping genomes; aiming telescopes, X-rays, and lasers; guiding industrial machines; organizing data; tests for microprocessors, job scheduling, and more.

$\endgroup$
0
$\begingroup$

The TSP often appears as part of more "complicated" operations research problems. A good example being the vehicle routing problem which has many variants. The following web site tracks some of the developments in this area:

http://neo.lcc.uma.es/vrp/vehicle-routing-problem/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.