INDEPENDENT DOMINATION IN ODD GRAPHS
No Thumbnail Available
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Saudi Digital Library
Abstract
الهيمنة في نظرية الرسم البياني تعتبر نموذج طبيعي لكثير من المشاكل المتعلقة بالمواقع في علوم الحاسوب وبحوث العمليات. العثور على الحد الأدنى لمجموعة مستقلة و مهيمنة في الرسوم البيانية العامة يعتبر من المشاكل الحدودية الغير محددة، و هذه المشكلة درست من قبل على نطاق واسع. في هذه الأطروحة، يتم عرض خوارزميات تقريبية للمرة الأولى لمجموعة مهيمنة و مستقلة في الرسم البياني الغريب. ويستند نهجنا على تقسيم الرسم البياني لمجموعات مختلفة من أجل تبسيط التعقيد في الرسم البياني والعثور على مجموعة مستقلة تهيمن على الأجزاء المقسمة من الرسم البياني، ثم دمج النتائج في حين حل أي اشكال في خصائص الاستقلال أو الهيمنة. وبالاضافة الى ذلك، نقدم نتائج تجريبية ومقارنة بين الخوارزميات التقريبية المقترحة و الخوارزميات الجشعة و العشوائية. نتائج التجارب تظهر أن الخوارزميات التقريبية المقترحة تعطي نتائج أفضل بالنسبة لحجم المجموعة وخصوصا على الرسوم البيانية الغريبة ذات الحجم الكبير.