این سایت در حال حاضر پشتیبانی نمی شود و امکان دارد داده های نشریات بروز نباشند
رایانش نرم و فناوری اطلاعات، جلد ۱۱، شماره ۲، صفحات ۱-۱۲
عنوان فارسی پیدا کردن مسیرهای همیلتونی بین دو رأس معین در گراف‌های توری T-شکل با اندازه زوج
چکیده فارسی مقاله یکی از مسایل مشهور در نظریه گراف، مسأله مسیر یا دور همیلتونی است. این مسأله برای گراف‌های عمومی و حتی برخی از کلاس‌های گراف‌ از جمله گراف‌های توری عمومی NP-کامل است. در این مقاله، مسأله پیدا‌کردن مسیر همیلتونی بین دو رأس ‌معین s و t در گرافهای توری T-شکل با اندازه زوج، که حالت خاصی از گراف های توری است، بررسی می‌شود. این مسأله کاربردهای مختلفی از جمله در ربات‌های جاروکننده و پردازش موازی دارد. در این مقاله، ابتدا شرایط لازم برای اینکه مسیر و دور همیلتونی وجود داشته باشد بیان می‌شود، سپس یک الگوریتم زمان خطی بر حسب اندازه گراف برای حل مسأله مسیر و دور همیلتونی ارائه می‌شود.
کلیدواژه‌های فارسی مقاله گراف توری، گراف توری T-شکل، مسیر همیلتونی، دور همیلتونی، NP-کامل،
عنوان انگلیسی Finding Hamiltonian Paths between Two Given Vertices in Even-sized T-shaped Grid Graphs
چکیده انگلیسی مقاله One of the most popular problems in graph theory is the Hamiltonian path or cycle problem. This problem is NP-complete for general graphs and even some classes of graphs, including general grid graphs. In this paper, we study the problem of finding a Hamiltonian path between two given vertices s and t in even-sized T-shaped grid graphs, which is special case of grid graphs. This problem has many applications including in sweeping robots and in parallel processing. In this paper, first we give necessary conditions for the existence of Hamiltonian paths and cycles, then we present a linear-time algorithm for solving these problem.
کلیدواژه‌های انگلیسی مقاله گراف توری, گراف توری T-شکل, مسیر همیلتونی, دور همیلتونی, NP-کامل
نویسندگان مقاله ریحانه فرقانی تهرانی |
گروه علوم کامپیوتر، دانشکده ریاضی و علوم کامپیوتر، دانشگاه شاهد، تهران ایران

فاطمه کشاورز کوهجردی |
گروه علوم کامپیوتر، دانشکده ریاضی و علوم کامپیوتر، دانشگاه شاهد، تهران، ایران

نشانی اینترنتی https://jscit.nit.ac.ir/article_149846_7b56b279af4a9cd2a94c17103f393a01.pdf
فایل مقاله فایلی برای مقاله ذخیره نشده است
کد مقاله (doi)
زبان مقاله منتشر شده fa
موضوعات مقاله منتشر شده
نوع مقاله منتشر شده
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات