نشر في جامعة البعث
بتاريخ 2016
في مجال
والبحث باللغة
العربية
تحميل البحث
الملخص بالعربية
كما هو معروف فإن مسألة تلوين بيان باستخدام أقل عدد من الألوان هي مسألة معقدة
(NP-Hard) المشكلة تتلخص في كيفية تلوين عقد بيان بأقل عدد ممكن من الألوان .
و بحيث لا يكون لأي عقدتين متجاورتين اللون نفسه، أو كيف يمكن تلوين أضلاع هذا
البيان بأقل عدد ممكن من الألون بحيث لا يكون لضلعين يشتركان بعقدة اللون نفسه.
نقدم في هذه الورقة البحثية خوارزمية تلوين جديدة لأضلاع بيان. هذه الخوارزمية تُمكننا
من الحصول على تلوين ضلعي مستمر لصف من البيانات الشهيرة.
المراجع المستخدمة
BARENBOIM, L.; ELKIN, M., 2009 - Distributed (Δ+1)-coloring in linear (in Δ) time, Proceedings of the 41st Symposium on Theory of Computing, pp. 111–120, ISBN 978-1-60558-506-2
BEIGEL, R., 2005 - 3-coloring in time O(1.3289n), Journal of Algorithms, 54 (2): 168–204
BRÉLAZ, D., 1979 - New Methods to Color the Vertices of a Graph, Communications of the ACM, 22 (4): 251–256