حل مساله رنگ آمیزی گراف با استفاده از الگوریتم جستجوی هارمونی

مهدی رضایی نژاد; سید عبدالمجید موسوی; مجید رحیمی نسب

حل مساله رنگ آمیزی گراف با استفاده از الگوریتم جستجوی هارمونی

محل انتشار: اولین کنفرانس ملی دانش پژوهان کامپیوتر و فناوری اطلاعات

سال انتشار: 1390

نوع سند: مقاله کنفرانسی

زبان: فارسی

مشاهده: 3,946

فایل این مقاله در 7 صفحه با فرمت PDF قابل دریافت می باشد

دریافت فایل کامل مقاله

صدور گواهی نمایه سازی
من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

https://civilica.com/doc/132148

شناسه ملی سند علمی:

CSCCIT01_169

تاریخ نمایه سازی: 8 بهمن 1390

چکیده مقاله:

مساله رنگ آمیزی گراف عبارت است از انتصاب K رنگ به رئوس یک گراف به صورتی که هیچ دو راس مجاور در گراف دارای رنگ یکسانی نباشند. کمترین تعداد رنگی که بتوان با آن یک گراف را رنگ آمیزی کرد ، عدد رنگی گراف نامیده می شود. یافتن عدد رنگی در مساله رنگ آمیزی گراف از جمله مسائل NP-COMPLETE می باشد لذا می توان از الگوریتم های تقریبی برای حل این مساله استفاده کرد. در این مقاله می خواهیم با استفاده از الگوریتم فرااکتشافی جستجوی هارمونی ، این مساله را حل کنیم. نتایچ به دست آمده از اجرای روش پیشنهادی روی گراف های تست DIMACS نشان دهنده کارایی بهتر این روش نسبت به الکوریتم های مورد مقایسه می باشد.

کلیدواژه ها:

مساله رنگ آمیزی گراف ، NP-COMPLETE ، گراف ، الگوریتم های فرا اکتشافی ، الگوریتم جستجوی هارمونی

نویسندگان

مهدی رضایی نژاد

دانشجوی کارشناسی ارشد نرم افزار-دانشگاه آزاد اسلامی واحد اراک- گروه کا

سید عبدالمجید موسوی

استادیار و عضو هیئت علمی دانشگاه لرستان

مجید رحیمی نسب

استادیار و عضو هیئت علمی دانشگاه لرستان

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :

Briggs, P., Cooper, K.D., Kennedy, K. and Torczon, L, "Coloring ...
Chaitin, G.J. "Register allocation and spilling via graph coloring", In ...
Chaitin, G.J., Auslander, M.A., Chandra, A.K. Cocke, J., Hopkins, M.E., ...
Wood, D.C., " A Technique for Coloring a Graph Applicable ...
De Werra, D., _ An Introduction to Timetabling", European Journal ...
Blum, A., _ Algorithms for Approximate Graph Coloring", PhD. Thesis, ...
Jobnson, D.S., Aragon, C.R., McGoach, L.A. and Schevon, C., "Optimization ...
Karger, D., Motwani, R. and Sudan, M. "Approximate Graph Coloring ...
Karp, R., "Reducibility among combinatoril problems", Complexity of computer computations, ...
Jensen TR. and Toft B., "Graph Coloring Problems", Wiley Interscience ...
Karapetyan, D., "Design, Evaluation and Analysis of C ombinatoria Optimization ...
Geem, Z.W., _ M usic-Inspired Harmony Search Algorithm", Springer, Vol ...
Brelaz, D., "New methods to color vertices of a graph", ...
Leighton, F.T., " A graph coloring algorithm for large scheduling ...
Halperin, E., Nathaniel, R., and Zwick, U., "Coloring k-Colorable Graphs ...
Costa, D. and Hertz, A., " Ants can color graphs", ...
Bessedik, M., Laib, R., Boulmerka, _ and Drias, H., " ...
Thang N. Bui, ThanhVu H Nguyen, Chirag M. Pateel _ ...
Salari, E. and Eshghi, K., " An ACGO Algorithm for ...
Li, Z., Liang, M.A. and Li, S., "Research of Graph ...
Akbari Torkestani, J. and Meybodi, M.R, "Graph Coloring Problem Based ...
Bouhmala, N. and Granmo, O.C., "Solving graph coloring problems using ...
Enami Eraghi, A., Akbari Torkestani, J. and Meybodi, M.R, "Cellular ...
Eberhart, R.C. and Shi, Y., "Evolving Artificial Neural Networks", Proceedings ...
Gudise, V.G., and Venayagamo orthy, G.K., "Comparison of Particle Swarm ...
Qin, J., Yin, Y. and Ban, X., "Hybrid Discrete Particle ...
Faraji, M. and Haj Seyyed Javadi, H., "Proposing a New ...
Glass, C.A. and Bennett A., "Genetic Algorithm for Graph Coloring: ...
Shen, J.W., "Solving the graph coloring problem using genetic programming ...
Abbasian, R. and Mouhoub, M., " An Efficient Hierarchical Parallel ...
Geem, Z.W., Kim, J.H., and Loganathan, G.V., " A New ...
Geem, Z.W., "Recent Advances in Harmony Search Algorithm", Springer, Vol ...
Wang, C.M. and Huang, Y.F., "Self-adaptive harmony search algorithm for ...
Jaberipour, M. and Khorram, E., "Two improved harmony search algorithms ...
Geem, Z.W., "Improved Harmony Search from Ensemble of Music Players", ...
http ://mat. gsia. cmu. edu/C OLOR02/ ...

نمایش کامل مراجع