Maximum clique conformance measure for graph coloring algorithms

العناوين الأخرى

مقياس توافق خوارزميات تلوين المخططات مع المخطط الجزئي الأعظم المكتمل الترابط

مقدم أطروحة جامعية

al-Zubi, Abd al-Muttalib Muhammad

مشرف أطروحة جامعية

Malkawi, Muhammad E.
Hassan, Muhammad M. al-Haj

أعضاء اللجنة

Rjub, Abd al-Rauf M.
Abu al-Hayja, Bilal

الجامعة

جامعة الشرق الأوسط

الكلية

كلية تكنولوجيا المعلومات

القسم الأكاديمي

قسم علم الحاسوب

دولة الجامعة

الأردن

الدرجة العلمية

ماجستير

تاريخ الدرجة العلمية

2011

الملخص الإنجليزي

The graph coloring problem (GCP) is an essential problem in graph theory [22], it has many applications such as the exam scheduling problem [38], register allocation problem[2], timetabling [15], and frequency assignment[19].

The maximum clique problem is also another important problem in graph theory and it arises in many real life applications like managing the social networks[7].

These two problems have received a lot of attention by the scientists, not only for their importance in the real life applications, but also for their theoretical sides [31,32,32,33,34,35,36].

Unfortunately, solving these problems is very complex, and the proposed algorithms for this purpose are able to solve only the small graphs with up to 80 nodes.

On the other hand and in order to module the real life applications we need graphs of hundreds or thousands of nodes.

This thesis presents a new algorithm for solving these hard problems, the new algorithm will run in a considerable time and it shows a competitive results for both of special purpose graphs as well as the general random graphs.

It also introduces a new measure for the deviation of the algorithms from maximum clique based coloring

التخصصات الرئيسية

تكنولوجيا المعلومات وعلم الحاسوب

عدد الصفحات

78

قائمة المحتويات

• APA
• MLA
• AMA

لغة النص

الإنجليزية

نوع البيانات

رسائل جامعية

رقم السجل

BIM-699571