Finding Hamiltonian Paths between Two Given Vertices in Even-sized T-shaped Grid Graphs

Fatemeh Keshavarz-Kohjerdi | R Forghani-Tehrani

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=169813
Date :  2022/09/22
Publish in :    رايانش نرم و فن اوري اطلاعات=Journal of Soft Computing and Information Technology

Link :  http://jscit.nit.ac.ir/article_149846.html
Keywords :گراف توري، گراف توري T-شکل، مسير هميلتوني، دور هميلتوني، NP-کامل

Abstract :

---

یکی از مساایل مشاوور در نظریه گراف، مسااله مسیر یا دور همیلتونی است . این مسااله برای گرافهای عمومی و حتی برخی از کلاسهای گراف از جمله گرافهای توری عمومی NP-کامل اسا . در این مقاله، مساله پیداکردن مسیر همیلتونی بین دو راس معین S و t در گرافهای توری T-شکل با اندازه زوج، که حالت خاصی از گرافهای توری است، بررسی میشود. این مسااله کاربردهای مختلفی از جمله در رباتهای جاروکننده و پردازش موازی دارد.