What are the practical application of Hamilton path& circuit? State Dirac’s and Ore’s theorems for a Hamilton circuit.
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.
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!!!
0 comments:
Post a Comment
Let us know your responses and feedback