Editing Hamiltonian path problem (section)

== Applications ==

=== Networks on chip ===
[[Network on a chip|Networks on chip]] (NoC) are used in computer systems and [[Processor (computing)|processors]] serving as communication for on-chip components.<ref>{{Cite web |last=Bahn |first=Jun Ho |title=Overview of Network-on-Chip |url=https://newport.eecs.uci.edu/~nader/lab/NoCOverview.htm |website=University Of California Irvine}}</ref> The performance of NoC is determined by the method it uses to move [[Network packet|packets]] of data across a [[Computer network|network]].<ref>{{Cite book |last=Satish |first=E. G. |title=Emerging Research in Computing, Information, Communication and Applications |chapter=Comparative Performance Analysis of Routing Topology for NoC Architecture |series=Lecture Notes in Electrical Engineering |date=2022 |chapter-url=https://link.springer.com/chapter/10.1007/978-981-16-1342-5_34 |volume=790 |pages=431–440 |doi=10.1007/978-981-16-1342-5_34 |isbn=978-981-16-1341-8 |via=Springer}}</ref> The Hamiltonian Path problem can be implemented as a path-based method in [[multicast routing]]. Path-based multicast algorithms will determine if there is a Hamiltonian path from the start [[Node (networking)|node]] to each end node and send packets across the corresponding path. Utilizing this strategy guarantees [[deadlock (computer science)|deadlock]] and [[livelock]] free routing, increasing the efficiency of the NoC.<ref>{{Cite journal |last1=Bahrebar |first1=P. |last2=Stroobandt |first2=D. |date=2014 |title=Improving hamiltonian-based routing methods for on-chip networks: A turn model approach |journal=2014 Design, Automation & Test in Europe Conference & Exhibition |pages=1–4 |via=IEEE}}</ref>

=== Computer graphics ===
[[Rendering (computer graphics)|Rendering]] engines are a form of [[software]] used in [[computer graphics]] to generate images or models from input data.<ref>{{Cite web |last1=Garsiel |first1=Tali |last2=Irish |first2=Paul |date=August 5, 2011 |title=How Browsers Work |url=https://web.dev/howbrowserswork/}}</ref>  In [[Three-dimensional space|three dimensional]] graphics rendering, a common input to the engine is a [[polygon mesh]]. The time it takes to render the object is dependent on the rate at which the input is received, meaning the larger the input the longer the rendering time. For triangle meshes, however, the rendering time can be decreased by up to a factor of three. This is done through "ordering the triangles so that consecutive triangles share a face."<ref>{{Cite journal |last1=Arkin |first1=Esther M. |last2=Mitchell |first2=Joseph S. B. |last3=Held |first3=Martin |last4=Skiena |first4=Steven S. |title=Hamiltonian Triangulations for Fast Rendering |url=https://www3.cs.stonybrook.edu/~stripe/compgeompaper.pdf |journal=Department of Computer Science Stony Brook University}}</ref> That way, only one vertex changes between each consecutive triangle. This ordering exists if the [[dual graph]] of the triangular mesh contains a Hamiltonian path.