INDEPENDENT DOMINATION IN ODD GRAPHS
| dc.contributor.author | AHMED AL-HERZ | |
| dc.date | 2012 | |
| dc.date.accessioned | 2022-05-18T04:43:17Z | |
| dc.date.available | 2022-05-18T04:43:17Z | |
| dc.degree.department | College of Computer Science and Engineering | |
| dc.degree.grantor | King Fahad for Petrolem University | |
| dc.description.abstract | الهيمنة في نظرية الرسم البياني تعتبر نموذج طبيعي لكثير من المشاكل المتعلقة بالمواقع في علوم الحاسوب وبحوث العمليات. العثور على الحد الأدنى لمجموعة مستقلة و مهيمنة في الرسوم البيانية العامة يعتبر من المشاكل الحدودية الغير محددة، و هذه المشكلة درست من قبل على نطاق واسع. في هذه الأطروحة، يتم عرض خوارزميات تقريبية للمرة الأولى لمجموعة مهيمنة و مستقلة في الرسم البياني الغريب. ويستند نهجنا على تقسيم الرسم البياني لمجموعات مختلفة من أجل تبسيط التعقيد في الرسم البياني والعثور على مجموعة مستقلة تهيمن على الأجزاء المقسمة من الرسم البياني، ثم دمج النتائج في حين حل أي اشكال في خصائص الاستقلال أو الهيمنة. وبالاضافة الى ذلك، نقدم نتائج تجريبية ومقارنة بين الخوارزميات التقريبية المقترحة و الخوارزميات الجشعة و العشوائية. نتائج التجارب تظهر أن الخوارزميات التقريبية المقترحة تعطي نتائج أفضل بالنسبة لحجم المجموعة وخصوصا على الرسوم البيانية الغريبة ذات الحجم الكبير. | |
| dc.identifier.other | 3953 | |
| dc.identifier.uri | https://drepo.sdl.edu.sa/handle/20.500.14154/1419 | |
| dc.language.iso | en | |
| dc.publisher | Saudi Digital Library | |
| dc.thesis.level | Master | |
| dc.thesis.source | King Fahad for Petrolem University | |
| dc.title | INDEPENDENT DOMINATION IN ODD GRAPHS | |
| dc.type | Thesis |