<p>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.</p>

CC BY-SA 3.0
2016-07-01T20:41:04.207Z
2016-07-01T20:41:04.207Z
David Eppstein
<ul>
<li>I think there are some applications in <em>electronic circuit design/construction</em>; for example <a href="http://dx.doi.org/10.1109/ASPDAC.2012.6165026" rel="noreferrer">Yi-Ming Wang, Shi-Hao Chen, Mango C. -T. Chao. An Efficient Hamiltonian-cycle power-switch routing for MTCMOS designs. 2012</a></li>
</ul>

<p><em>Abstract</em>: 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. ...</p>

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

<p><a href="https://i.sstatic.net/wIauf.png" rel="noreferrer"><img src="https://i.sstatic.net/wIauf.png" alt="enter image description here"></a></p>

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

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

CC BY-SA 3.0
2016-07-04T07:16:54.407Z
2016-07-04T08:05:06.133Z
2016-07-04T08:05:06.133Z
Marzio De Biasi
<p>(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 <a href="http://press.princeton.edu/titles/9531.html" rel="noreferrer">In Pursuit of the Traveling Salesman:
Mathematics at the Limits of Computation</a> 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.</p>

CC BY-SA 3.0
2016-07-11T16:50:53.200Z
2016-07-11T16:50:53.200Z
kbala
<p>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:</p>

<p><a href="http://neo.lcc.uma.es/vrp/vehicle-routing-problem/" rel="nofollow noreferrer">http://neo.lcc.uma.es/vrp/vehicle-routing-problem/</a></p>

CC BY-SA 3.0
2017-01-16T21:52:35.807Z
2017-01-16T21:52:35.807Z
Joseph Malkevitch
<p>The Hamiltonian Cycle Problem and Travelling Salesman Problem are among famous NP-complete problems and has been studied extensively.</p>

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

CC BY-SA 3.0
2016-07-01T22:59:11.773Z
Few years ago, it was useful in genome sequencing.
Saeed
<graph-theory><application-of-theory><hamiltonian-paths>
Applications of Hamiltonian Cycle Problem
user136457
# Applications of Hamiltonian Cycle Problem

(Asked by: username_0 on 2016-07-01)

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?

**Tags:** graph-theory, application-of-theory, hamiltonian-paths
> **Comments:**
> **username_1**: Few years ago, it was useful in genome sequencing.  

---

## 4 answers

### Answer by username_2 on 2016-07-01. Score: 8

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.


---

### Answer by username_3 on 2016-07-04. Score: 7

* I think there are some applications in *electronic circuit design/construction*; for example [Yi-Ming Wang, Shi-Hao Chen, Mango C. -T. Chao. An Efficient Hamiltonian-cycle power-switch routing for MTCMOS designs. 2012](http://dx.doi.org/10.1109/ASPDAC.2012.6165026)

*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](https://i.sstatic.net/wIauf.png)](https://i.sstatic.net/wIauf.png)

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!!!


---

### Answer by username_4 on 2016-07-11. Score: 5

(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](http://press.princeton.edu/titles/9531.html) 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.


---

### Answer by username_5 on 2017-01-16. Score: 0

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/>


---

