Improvement of the DSATUR algorithm for graph coloring
المؤلف | Jaam, Jihad M. |
المؤلف | Hasnah, Ahmad M. |
تاريخ الإتاحة | 2024-03-20T01:55:10Z |
تاريخ النشر | 2003 |
اسم المنشور | Arab Gulf Journal of Scientific Research |
المصدر | Scopus |
الرقم المعياري الدولي للكتاب | 19859899 |
الملخص | In this paper we discuss the deterministic Brelaz's DSATUR algorithm for graph coloring. We propose a simple modification that improves the performance of the algorithm. This modification consists of assigning the color that saturates the least number of uncolored vertices, to the selected vertex. Thus, we obtain valid k-colorings better than those obtained with DSATUR without modification. We show also that the DSATUR algorithm is optimal, for a given example, and for the bipartite graphs. |
اللغة | en |
الناشر | Arabian Gulf University |
الموضوع | Algorithm DSATUR Graph coloring Lipartite graphs |
النوع | Article |
الصفحات | 90-94 |
رقم العدد | 2 |
رقم المجلد | 21 |
الملفات في هذه التسجيلة
الملفات | الحجم | الصيغة | العرض |
---|---|---|---|
لا توجد ملفات لها صلة بهذه التسجيلة. |
هذه التسجيلة تظهر في المجموعات التالية
-
علوم وهندسة الحاسب [2402 items ]