Maximum clique conformance measure for graph coloring algorithms
Other Title(s)
مقياس توافق خوارزميات تلوين المخططات مع المخطط الجزئي الأعظم المكتمل الترابط
Dissertant
al-Zubi, Abd al-Muttalib Muhammad
Thesis advisor
Malkawi, Muhammad E.
Hassan, Muhammad M. al-Haj
Comitee Members
Rjub, Abd al-Rauf M.
Abu al-Hayja, Bilal
University
Middle East University
Faculty
Faculty of Information Technology
Department
Computer Science Department
University Country
Jordan
Degree
Master
Degree Date
2011
English Abstract
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
Main Subjects
Information Technology and Computer Science
No. of Pages
78
Table of Contents
Table of contents.
Abstract.
Abstract in Arabic.
Chapter One : Introduction.
Chapter Two : Literature survey.
Chapter Three : The modified graph coloring algorithm.
Chapter Four : Implementation.
Chapter Five : Complexity and performance analysis.
Chapter Six : Conclusions and future works.
References.
American Psychological Association (APA)
al-Zubi, Abd al-Muttalib Muhammad. (2011). Maximum clique conformance measure for graph coloring algorithms. (Master's theses Theses and Dissertations Master). Middle East University, Jordan
https://search.emarefa.net/detail/BIM-699571
Modern Language Association (MLA)
al-Zubi, Abd al-Muttalib Muhammad. Maximum clique conformance measure for graph coloring algorithms. (Master's theses Theses and Dissertations Master). Middle East University. (2011).
https://search.emarefa.net/detail/BIM-699571
American Medical Association (AMA)
al-Zubi, Abd al-Muttalib Muhammad. (2011). Maximum clique conformance measure for graph coloring algorithms. (Master's theses Theses and Dissertations Master). Middle East University, Jordan
https://search.emarefa.net/detail/BIM-699571
Language
English
Data Type
Arab Theses
Record ID
BIM-699571
