Shahed University

The Hamiltonian path problem in an odd-sized L-shaped grid graphs with a rectangular grid graph

Mehran Zali-Ghehi | Fatemeh Keshavarz-Kohjerdi

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=127106
Date :  2019/11/20
Publish in :    4th International Conference on Combinatorics, Cryptography, Computer Science and Computing


Keywords :گراف توري، مسير هميلتوني، گراف توري L-شکل با يک حفره مستطيلي، NP-کامل

Abstract :
مساله مسیر همیلتونی یکی از مسایل NP-کامل مشهور در نظریه گراف‌ها است که برای بسیاری از کلاس‌ گراف‌ها از جمله گراف‌های توری عمومی نیز این مساله NP-کامل است. گراف توری یک زیرگراف راس القایی محدود از یک گراف نامتناهی است که مجموعه رئوس ان تمام نقاط صفحه با مختصات صحیح می¬باشد و دو راس از طریق یالی به هم متصل هستند اگر و تنها اگر فاصله اقلیدسی بین ان¬ها یک باشد. در این مقاله، مساله مسیر همیلتونی بین دو راس معین s و t در گراف‌های توری L-شکل با یک حفره مستطیلی به طوری که اندازه کل گراف فرد است را بررسی می‌کنیم.



Files in this item :
Download Name : 127106_14122239236.pdf
Size : 922Kb
Format : PDF