مجموعة مهيمنة

في نظرية المخططات ، تُعرف المجموعة المهيمنة للمخطط G بأنها مجموعة جزئية D من رؤوسه، بحيث يكون أي رأس من رؤوس G موجودًا في D ، أو له جار في D. ويُعرف عدد الهيمنة γ ( G ) بأنه عدد الرؤوس في أصغر مجموعة مهيمنة للمخطط G.

تتعلق مسألة المجموعة المهيمنة باختبار ما إذا كانت γ( G ) ≤ K لرسم بياني مُعطى G ومدخل K ؛ وهي مسألة قرار كلاسيكية من فئة NP-كاملة في نظرية التعقيد الحسابي . ^{[ 1 ]} لذلك، يُعتقد أنه قد لا توجد خوارزمية فعالة لحساب γ( G ) لجميع الرسوم البيانية G. ومع ذلك، توجد خوارزميات تقريبية فعالة ، بالإضافة إلى خوارزميات دقيقة فعالة لفئات معينة من الرسوم البيانية.

تُعدّ المجموعات المهيمنة ذات أهمية عملية في العديد من المجالات. ففي الشبكات اللاسلكية ، تُستخدم هذه المجموعات لإيجاد مسارات فعّالة ضمن الشبكات المتنقلة المخصصة. كما استُخدمت أيضاً في تلخيص المستندات ، وفي تصميم أنظمة آمنة للشبكات الكهربائية .

ترتبط المجموعات المهيمنة ارتباطًا وثيقًا بالمجموعات المستقلة : فالمجموعة المستقلة هي أيضًا مجموعة مهيمنة إذا وفقط إذا كانت مجموعة مستقلة قصوى ، لذلك فإن أي مجموعة مستقلة قصوى في الرسم البياني هي بالضرورة أيضًا مجموعة مهيمنة دنيا.

بالنظر إلى رسم بياني غير موجه G = ( V , E ) ، فإن مجموعة فرعية من الرؤوس${\displaystyle D\subseteq V}$تُسمى مجموعة مهيمنة إذا كان لكل رأس${\displaystyle u\in V\setminus D}$، هناك رأس${\displaystyle v\in D}$بحيث${\displaystyle \{u,v\}\in E}$.

يحتوي كل رسم بياني على مجموعة مهيمنة واحدة على الأقل: إذا${\displaystyle D=V=}$إذا كانت D مجموعة جميع الرؤوس، فإن تعريفها هو مجموعة مهيمنة، لأنه لا يوجد رأس${\displaystyle u\in V\setminus D}$يتمثل التحدي الأكثر إثارة للاهتمام في إيجاد مجموعات مهيمنة صغيرة. يُعرَّف عدد الهيمنة للمجموعة G على النحو التالي:${\displaystyle \gamma (G):=\min\{|D|:D{\text{ is a dominating set of }}G\}}$.

دُرست مسألة الهيمنة منذ خمسينيات القرن العشرين، لكن وتيرة البحث فيها ازدادت بشكل ملحوظ في منتصف سبعينيات القرن نفسه. في عام ١٩٧٢، أثبت ريتشارد كارب أن مسألة تغطية المجموعات هي مسألة كاملة من فئة NP . كان لهذا الاكتشاف آثار مباشرة على مسألة المجموعة المهيمنة، إذ توجد تقابلات مباشرة بين الرؤوس والمجموعات، وبين الحواف والتقاطعات غير المنفصلة، ​​بين المسألتين. وقد أثبت هذا أن مسألة المجموعة المهيمنة هي مسألة كاملة من فئة NP أيضًا. ^{[ ٢ ]}

تُعدّ مسألة تغطية المجموعات مسألةً معروفةً من مسائل NP-hard ، وكانت صيغة القرار منها إحدى مسائل كارب الـ 21 من مسائل NP-complete . يوجد زوج من اختزالات L-reductions ذات زمن متعدد الحدود بين مسألة المجموعة المهيمنة الدنيا ومسألة تغطية المجموعات . ^{[ 3 ]} تُظهر هذه الاختزالات ( انظر أدناه ) أن خوارزمية فعّالة لمسألة المجموعة المهيمنة الدنيا ستوفر خوارزمية فعّالة لمسألة تغطية المجموعات، والعكس صحيح. علاوةً على ذلك، تحافظ هذه الاختزالات على نسبة التقريب : لأي قيمة α، فإن خوارزمية تقريب α ذات زمن متعدد الحدود للمجموعات المهيمنة الدنيا ستوفر خوارزمية تقريب α ذات زمن متعدد الحدود لمسألة تغطية المجموعات، والعكس صحيح. كلتا المسألتين في الواقع من مسائل Log-APX-complete . ^{[ 4 ]}

إن إمكانية تقريب تغطية المجموعات مفهومة جيدًا: يمكن إيجاد عامل تقريب لوغاريتمي باستخدام خوارزمية جشعة بسيطة ، بينما يُعد إيجاد عامل تقريب دون لوغاريتمي مسألة صعبة من نوع NP. وبشكل أكثر تحديدًا، توفر الخوارزمية الجشعة تقريبًا بمعامل 1 + log | V | لمجموعة مهيمنة دنيا، ولا يمكن لأي خوارزمية ذات زمن متعدد الحدود تحقيق عامل تقريب أفضل من c log | V | لبعض c > 0 إلا إذا كانت P = NP . ^{[ 5 ]}

اختزالات L

يوضح الاختزالان التاليان أن مسألة مجموعة الهيمنة الدنيا ومسألة تغطية المجموعة متكافئتان في ظل اختزالات L : فبإعطاء حالة من إحدى المسألتين، يمكننا إنشاء حالة مكافئة للمسألة الأخرى. ^{[ 3 ]}

من السيطرة على موقع التصوير إلى تغطية موقع التصوير

بالنظر إلى الرسم البياني G = ( V , E ) مع V = {1, 2, ..., n }، قم بإنشاء مثال غطاء المجموعة ( U , S ) على النحو التالي: الكون U هو V ، وعائلة المجموعات الفرعية هي S ₌ { S1 , S2 _, ..., Sn _} بحيث تتكون Sv من الرأس _v وجميع الرؤوس المجاورة لـ v في G.

إذا كانت D مجموعة مهيمنة على G ، فإن C = { S _v  : v ∈ D } حل ممكن لمسألة تغطية المجموعة، حيث | C | = | D | . وبالعكس، إذا كانت C = { S _v  : v ∈ D } حلاً ممكناً لمسألة تغطية المجموعة، فإن D مجموعة مهيمنة على G ، حيث | D | = | C | .

وبالتالي، فإن حجم أصغر مجموعة مهيمنة لـ G يساوي حجم أصغر غطاء مجموعة لـ ( U , S ) . علاوة على ذلك، توجد خوارزمية بسيطة تربط مجموعة مهيمنة بغطاء مجموعة من نفس الحجم والعكس صحيح. على وجه الخصوص، توفر خوارزمية تقريب ألفا فعالة لتغطية المجموعات خوارزمية تقريب ألفا فعالة لمجموعات الهيمنة الدنيا.

_{على سبيل المثال، بالنظر} إلى الرسم البياني G الموضح على اليمين، نقوم بإنشاء حالة تغطية مجموعة مع الكون U = {1, 2, ..., 6} والمجموعات الجزئية S1 = {1, 2, 5}، _{S2 = {1, 2, 3, 5}، S3} = _{ 2 , 3, 4, 6}، _S4 = { ₃ , 4}، _S5 = {1, 2, 5, 6}، و S6 = {3, _{5 , 6} }. في هذا المثال، D = {3, 5} هي مجموعة مهيمنة على G - وهذا يقابل تغطية المجموعة C = { S3 , S5 }. على سبيل المثال، يهيمن الرأس 3 ∈ D على الرأس 4 ∈ V ، والعنصر 4 ∈ U موجود في المجموعة S3 _∈ C.

من تغطية الديكور إلى السيطرة على الديكور

ليكن ( S , U ) مثالًا على مسألة تغطية المجموعات، حيث U هي المجموعة الشاملة و _S هي مجموعة جزئية من المجموعات S = { Sᵢ : i ∈ I }.  نفترض أن U ومجموعة الفهارس I منفصلتان. أنشئ الرسم البياني G = ( V , E ) كما يلي: مجموعة الرؤوس هي V = I ∪ U ، يوجد ضلع { i , j } ∈ E بين كل زوج i , j ∈ I ، ويوجد أيضًا ضلع { i , u } لكل i ∈ I و u ∈ Sᵢ _. أي أن G رسم بياني منقسم : I هي زمرة و U هي مجموعة مستقلة .

إذا كانت C = { S _i  : i ∈ D } حلاً ممكناً لمسألة تغطية المجموعة لمجموعة جزئية D ⊆ I ، فإن D هي مجموعة مهيمنة على G ، حيث | D | = | C | : أولاً، لكل u ∈ U يوجد i ∈ D بحيث u ∈ S _i ، وبحسب التعريف، فإن u و i متجاوران في G ؛ لذا فإن u مهيمنة بواسطة i . ثانياً، بما أن D يجب أن تكون غير فارغة، فإن كل i ∈ I مجاور لرأس في D.

على العكس، ليكن D مجموعة مهيمنة لـ G. عندئذٍ ، من الممكن إنشاء مجموعة مهيمنة أخرى X بحيث يكون | X | ≤ | D | و X ⊆ I : ببساطة، استبدل كل u ∈ D ∩ U بجاره i ∈ I. عندئذٍ، C = { S _i : i ∈ X } هو حل ممكن لمسألة تغطية المجموعة، حيث | C | = | X | ≤ | D | . 

يوضح الرسم التوضيحي على اليمين كيفية إنشاء U = { a , b , c , d , e }, I = {1, 2, 3, 4}, S ₁ = { a , b , c }, S ₂ = { a , b }, S ₃ = { b , c , d }, و S ₄ = { c , d , e }.

في هذا المثال، C = { S ₁ , S ₄ } هي مجموعة تغطية؛ وهذا يتوافق مع المجموعة المهيمنة D = {1, 4}.

D = { a , 3, 4} هي مجموعة مهيمنة أخرى للرسم البياني G. بمعرفة D ، يمكننا إنشاء مجموعة مهيمنة X = {1, 3, 4} لا تكون أكبر من D وهي مجموعة جزئية من I. تتوافق المجموعة المهيمنة X مع غطاء المجموعة C = { S ₁ , S ₃ , S ₄ }.

المجموعة المهيمنة المستقلة هي مجموعة مهيمنة هي أيضًا مجموعة مستقلة ، أو بصورة مكافئة، مجموعة مستقلة قصوى . عدد الهيمنة المستقلة${\displaystyle i(G)}$يمثل الحد الأدنى لحجم مجموعة مهيمنة مستقلة في G. وبما أن الحد الأدنى يُحسب على عدد أقل من المجموعات،${\displaystyle \gamma (G)\leq i(G)}$بالنسبة لجميع الرسوم البيانية G ، ويمكن أن تكون المتباينة صارمة. تتحقق المساواة للرسوم البيانية الخالية من المخالب ؛ ^{[ 15 ]} بما أن كل رسم بياني خطي خالٍ من المخالب، فإنه يترتب على ذلك أن الحد الأدنى للمطابقة القصوى والحد الأدنى لمجموعة هيمنة الحواف لأي رسم بياني لهما نفس الحجم.

مجموعة استقلال مهيمنة للرسم البياني${\displaystyle G}$هي مجموعة تهيمن على كل مجموعة مستقلة من${\displaystyle G}$عدد هيمنة الاستقلال${\displaystyle i\gamma (G)}$هو الحد الأقصى، على جميع المجموعات المستقلة${\displaystyle A}$ل${\displaystyle G}$، من أصغر مجموعة مهيمنة${\displaystyle A}$[ ^{16 ]} إن السيطرة على مجموعات مستقلة فقط تتطلب عددًا أقل من الرؤوس مقارنةً بالسيطرة على جميع الرؤوس، ^لذلك${\displaystyle i\gamma (G)\leq \gamma (G)}$لجميع الرسوم البيانية${\displaystyle G}$والنسبة${\displaystyle \gamma (G)/i\gamma (G)}$يمكن أن تكون كبيرة بشكل تعسفي. ^{[ 16 ]}

المجموعة المهيمنة المتصلة هي مجموعة مهيمنة متصلة أيضاً .${\displaystyle S}$إذا كانت مجموعة مهيمنة متصلة، فيمكن للمرء تكوين شجرة ممتدة من${\displaystyle G}$في أي${\displaystyle S}$يشكل مجموعة الرؤوس غير الورقية للشجرة؛ والعكس صحيح، إذا${\displaystyle T}$هي أي شجرة ممتدة في رسم بياني يحتوي على أكثر من رأسين، وهما الرأسان غير الورقيين لـ${\displaystyle T}$تشكل مجموعة مهيمنة متصلة. لذلك، فإن إيجاد أصغر مجموعة مهيمنة متصلة يعادل إيجاد أشجار ممتدة بأكبر عدد ممكن من الأوراق.

مجموعة الهيمنة الكلية هي مجموعة من الرؤوس بحيث يكون لكل رأس في الرسم البياني، بما في ذلك الرؤوس الموجودة في مجموعة الهيمنة نفسها، جار في مجموعة الهيمنة. ^{[ 17 ]} أي: لكل رأس${\displaystyle u\in V}$، هناك رأس${\displaystyle v\in D}$بحيث${\displaystyle \{u,v\}\in E}$يوضح الشكل (ج) أعلاه مجموعة مهيمنة متصلة ومجموعة مهيمنة كلية؛ أما الأمثلة في الشكلين (أ) و(ب) فلا تمثل أيًا منهما. على عكس المجموعة المهيمنة البسيطة، قد لا توجد مجموعة مهيمنة كلية. على سبيل المثال، لا يمتلك الرسم البياني الذي يحتوي على رأس واحد أو أكثر ولا يحتوي على حواف مجموعة مهيمنة كلية. عدد الهيمنة الكلية${\displaystyle \gamma ^{\text{total}}(G)}$يُعرَّف بأنه الحد الأدنى لحجم مجموعة الهيمنة الكلية لـ G ؛ من الواضح،${\displaystyle \gamma ^{\text{total}}(G)\geq \gamma (G)}$.

مجموعة الحواف المهيمنة هي مجموعة من الحواف (أزواج الرؤوس) التي يشكل اتحادها مجموعة مهيمنة؛ وقد لا توجد مثل هذه المجموعة (على سبيل المثال، لا يمتلكها رسم بياني يحتوي على رأس واحد أو أكثر ولا يحتوي على حواف). إذا وُجدت، فإن اتحاد جميع حوافها يشكل مجموعة مهيمنة كلية. لذلك، فإن أصغر حجم لمجموعة الحواف المهيمنة هو على الأقل${\displaystyle \gamma ^{\text{total}}(G)/2}$.

في المقابل، فإن المجموعة التي تهيمن عليها الحواف هي مجموعة${\displaystyle D}$من الحواف، بحيث لا تكون كل حافة في${\displaystyle D}$يقع بجوار حافة واحدة على الأقل في${\displaystyle D}$; توجد مثل هذه المجموعة دائمًا (على سبيل المثال، مجموعة جميع الحواف هي مجموعة تهيمن على الحواف).

مجموعة الهيمنة من الرتبة k هي مجموعة من الرؤوس بحيث يكون لكل رأس غير موجود في المجموعة k جار على الأقل في المجموعة (مجموعة الهيمنة القياسية هي مجموعة هيمنة من الرتبة 1). وبالمثل، فإن مجموعة الهيمنة من الرتبة k هي مجموعة من الرؤوس بحيث يكون لكل رأس في الرسم البياني k جار على الأقل في المجموعة (مجموعة الهيمنة الكلية هي مجموعة هيمنة من الرتبة 1). يمكن إيجاد تقريب (1 +  log n ) لمجموعة الهيمنة الدنيا من الرتبة k في وقت متعدد الحدود. ^{[ 18 ]} كل رسم بياني يقبل مجموعة هيمنة من الرتبة k (على سبيل المثال، مجموعة جميع الرؤوس)؛ ولكن الرسوم البيانية ذات الدرجة الدنيا k − 1 فقط هي التي تقبل مجموعة هيمنة من الرتبة k . ومع ذلك، حتى لو كان الرسم البياني يقبل مجموعة هيمنة من الرتبة k ، فقد تكون مجموعة الهيمنة الدنيا من الرتبة k أكبر بحوالي k مرة من مجموعة الهيمنة الدنيا من الرتبة k لنفس الرسم البياني؛ ^{[ 19 ]} يمكن إيجاد تقريب (1.7 + log Δ) لمجموعة k- المهيمنة الدنيا في وقت متعدد الحدود أيضًا.

تُعرَّف المجموعة المهيمنة الكسرية من خلال دالة مهيمنة كسرية ، وهي دالة${\displaystyle f:V(G)\to [0,1]}$بحيث يكون لكل رأس${\displaystyle v\in V}$، مجموع${\displaystyle f}$فوق الحي المغلق${\displaystyle N[v]}$هو 1 على الأقل. ^{[ 20 ]} عدد الهيمنة الجزئية${\displaystyle \gamma _{f}(G)}$يمثل الحد الأدنى للوزن الإجمالي (مجموع قيم جميع الرؤوس) لهذه الدالة، ويحقق${\displaystyle \gamma _{f}(G)\leq \gamma (G)}$لـ${\displaystyle k}$- رسم بياني منتظم مع${\displaystyle n}$الرؤوس (${\displaystyle k\geq 1}$، يساوي عدد الهيمنة الجزئية${\displaystyle n/(k+1)}$.

المجموعة التي يهيمن عليها النجم هي مجموعة جزئية${\displaystyle D}$ل${\displaystyle V}$بحيث يكون لكل رأس${\displaystyle v}$في${\displaystyle V}$، نجم​${\displaystyle v}$(مجموعة الحواف المجاورة لـ${\displaystyle v}$) يتقاطع مع نجمة رأس ما في${\displaystyle D}$من الواضح، إذا${\displaystyle G}$إذا كانت تحتوي على رؤوس معزولة، فلن تحتوي على مجموعات مهيمنة على النجمة (لأن نجمة الرؤوس المعزولة فارغة).${\displaystyle G}$إذا لم يكن للمجموعة رؤوس معزولة، فإن كل مجموعة مهيمنة هي مجموعة مهيمنة نجمية، والعكس صحيح. ويكون التمييز بين الهيمنة النجمية والهيمنة العادية أكثر وضوحًا عند النظر في متغيراتهما الكسرية. ^{[ 21 ]}

التقسيم الدوماتي هو تقسيم الرؤوس إلى مجموعات مهيمنة منفصلة. العدد الدوماتي هو الحد الأقصى لحجم التقسيم الدوماتي.

مجموعة الهيمنة الأبدية هي نسخة ديناميكية من الهيمنة حيث يكون الرأس${\displaystyle v}$في مجموعة مهيمنة${\displaystyle D}$يتم اختياره واستبداله بجار${\displaystyle u}$(${\displaystyle u}$ليس في${\displaystyle D}$) بحيث يكون المعدل${\displaystyle D}$وهي أيضًا مجموعة مهيمنة، ويمكن تكرار هذه العملية على أي سلسلة لانهائية من اختيارات الرؤوس. ${\displaystyle v}$.

مجموعة الهيمنة الفعالة (وتسمى أيضاً مجموعة ed أو مجموعة الهيمنة الكاملة المستقلة ^{[ 22 ]} ) هي مجموعة هيمنة تتميز بخاصية إضافية، وهي أن كل رأس في الرسم البياني يهيمن عليه رأس واحد فقط في المجموعة. ^{[ 23 ]}

تُعرَّف مجموعة الهيمنة الرومانية من خلال دالة الهيمنة الرومانية ، التي تُسند لكل رأس قيمة من${\displaystyle \{0,1,2\}}$بحيث يكون كل رأس مُخصَّص له القيمة 0 مجاورًا لرأس واحد على الأقل مُخصَّص له القيمة 2. رقم الهيمنة الرومانية${\displaystyle \gamma _{R}(G)}$هو الحد الأدنى لمجموع قيم جميع الرؤوس على جميع هذه الدوال. هذا المفهوم مستوحى من استراتيجية دفاعية للإمبراطورية الرومانية، حيث تمثل الرؤوس المدن وتمثل القيم الفيالق المتمركزة. لأي رسم بياني${\displaystyle G}$،${\displaystyle \gamma (G)\leq \gamma _{R}(G)\leq 2\gamma (G)}$، مع تحقيق الحد الأدنى فقط بواسطة الرسم البياني الفارغ . ^{[ 24 ]}

مجموعة الهيمنة العالمية هي مجموعة مهيمنة على الرسم البياني${\displaystyle G}$وهي أيضاً مجموعة مهيمنة على الرسم البياني المكمل${\displaystyle {\overline {G}}}$رقم الهيمنة العالمية${\displaystyle \gamma _{g}(G)}$هو الحد الأدنى لعدد عناصر المجموعة المهيمنة العالمية. أو بعبارة أخرى، مجموعة مهيمنة${\displaystyle S}$تكون مجموعة مهيمنة عالمية إذا وفقط إذا كان لكل رأس${\displaystyle v\in V-S}$يوجد رأس${\displaystyle u\in S}$بحيث${\displaystyle u}$ليس مجاورًا لـ${\displaystyle v}$بحسب التعريف،${\displaystyle \gamma _{g}(G)=\gamma _{g}{\big (}{\overline {G}}{\big )}}$و${\displaystyle \gamma (G)\leq \gamma _{g}(G)}$. للرسم البياني${\displaystyle G}$مع${\displaystyle p}$الرؤوس،${\displaystyle \gamma _{g}(G)=p}$إذا وفقط إذا${\displaystyle G=K_{p}}$أو${\displaystyle G={\overline {K_{p}}}}$[ ^{25 ]​}

المجموعة المهيمنة المعتمدة هي مجموعة مهيمنة يكون لكل رأس فيها إما صفر أو جارين على الأقل خارج المجموعة. ^{[ 26 ]} عدد الهيمنة المعتمدة${\displaystyle \gamma _{\text{cer}}(G)}$هو الحد الأدنى لحجم مجموعة مهيمنة معتمدة. من الواضح،${\displaystyle \gamma _{\text{cer}}(G)\geq \gamma (G)}$وتتحقق المساواة عندما لا يحتوي الرسم البياني على رأس دعم ضعيف (على وجه الخصوص، عندما${\displaystyle \delta (G)\geq 2}$بالنسبة للرسم البياني المتصل،${\displaystyle \gamma _{\text{cer}}(G)\leq 2\gamma (G)}$.

مجموعة مهيمنة مزدوجة في الرسم البياني${\displaystyle G=(V,E)}$مجموعة مهيمنة${\displaystyle S}$من الرؤوس بحيث يكون الرسم البياني الفرعي المستحث${\displaystyle G[S]}$يحتوي على تطابق تام واحد على الأقل . ^{[ 27 ]} عدد الهيمنة المزدوجة${\displaystyle \gamma _{p}(G)}$هو الحد الأدنى لعدد عناصر مجموعة مهيمنة مزدوجة من${\displaystyle G}$. يمثل هذا المفهوم حالة يتم فيها وضع الحراس عند رؤوس الرسم البياني للسيطرة (حماية) جميع الرؤوس، مع القيد الإضافي المتمثل في تعيين حارس مجاور آخر كنسخة احتياطية لكل حارس.

وتشمل المتغيرات الأخرى

• مجموعة مهيمنة مقيدة، ^{[ 28 ]}
• مجموعة الهيمنة الآمنة، ^{[ 29 ]}
• مجموعة مهيمنة متصلة ثلاثياً، ^{[ 30 ]}
• مجموعة مهيمنة موقعة، ^{[ 31 ]}
• مجموعة الهيمنة السالبة، ^{[ 32 ]} و
• مجموعة مهيمنة ودودة. ^{[ 33 ]}

• تخمين فيزينغ – يربط عدد الهيمنة لحاصل الضرب الديكارتي للرسوم البيانية بعدد الهيمنة لعوامله
• مشكلة غلاف المجموعة
• رقم العبودية
• غير حاجب – مكمل لمجموعة مهيمنة
• الرأس الشامل – مجموعة مهيمنة ذات رأس واحد

• أهاروني، رون؛ بيرغر، ايلي. زيف ، ران (2007-05-01). “الأنظمة المستقلة للممثلين في الرسوم البيانية المرجحة”. كومبيناتوريكا . 27 (3): 253-267 . دوى : 10.1007 / s00493-007-2086-y . ردمك 1439-6912 . S2CID 43510417 .  
• ألبر، يوشين؛ فيلوز، مايكل ر ؛ نيدرماير، رولف (2004)، "اختزال البيانات في وقت متعدد الحدود لمجموعة الهيمنة"، مجلة ACM ، 51 (3): 363-384 ، arXiv : cs/0207066 ، doi : 10.1145/990308.990309 ، S2CID 488501 .
• ألان، روبرت ب.؛ لاسكار، رينو (1978)، "حول الهيمنة وأعداد الهيمنة المستقلة للرسم البياني"، الرياضيات المتقطعة ، 23 (2): 73-76 ، doi : 10.1016/0012-365X(78)90105-X.
• بانج، د. و.؛ باركاوسكاس، أ. إ.؛ سلاتر، ب. ج. (1988). "مجموعات الهيمنة الفعالة في الرسوم البيانية". تطبيقات الرياضيات المتقطعة . فيلادلفيا: سيام. ص 189-199 . 
• براندشتات، أندرياس؛ لايترت، آرني؛ راوتنباخ، ديتر (2012). "مجموعات الهيمنة الفعالة ومجموعات هيمنة الحواف للرسوم البيانية والرسوم البيانية الفائقة". الخوارزميات والحوسبة . سلسلة محاضرات في علوم الحاسوب. المجلد  7676. برلين، هايدلبرغ: سبرينغر. الصفحات 267-277 . arXiv : 1207.0953 . doi : 10.1007/978-3-642-35261-4_30 . ISBN  978-3-642-35261-4.
• كاباهوغ الابن، آي إس؛ إيبال، آر جي؛ فرنانديز، آر تي (2025). "الهيمنة الودية في الرسم البياني" . المجلة الأوروبية للرياضيات البحتة والتطبيقية . 18 (4): 1-15 . doi : 10.29020/nybg.ejpam.v18i4.6326 .
• كوكاين، إي جيه؛ دراير، بي إيه؛ هيديتنييمي، إس إم؛ هيديتنييمي، إس تي (2004). "الهيمنة الرومانية في الرسوم البيانية". الرياضيات المتقطعة . 278 ( 1-3 ): 11-22 . doi : 10.1016/j.disc.2003.06.004 .
• كريسينزي، بييرلويجي؛ كان، فيجو؛ هالدورسون، ماغنوس؛ الأماكن القريبة : Woeginger، Gerhard (2000)، “الحد الأدنى من المجموعة المهيمنة”، خلاصة وافية لمشاكل تحسين NP.
• دين، فرانك؛ فيلوز، مايكل؛ فيرناو، هينينغ؛ برييتو، إيلينا ؛ روزاموند، فرانسيس (2006)، "Nonblocker: Parameterized algorithmics for minimum domination set" (ملف PDF) ، SOFSEM 2006: المؤتمر الثاني والثلاثون حول الاتجاهات الحالية في نظرية وممارسة علوم الحاسوب، ميرين، جمهورية التشيك، 21-27 يناير 2006، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب، المجلد  3831، سبرينغر، الصفحات 237-245 ، doi : 10.1007/11611257_21 ، ISBN  978-3-540-31198-0.
• ديتلاف، ماجدة. ليمانسكا، ماغدالينا؛ توب، جيرزي. زيمان، رادوسلاف؛ زيلينسكي ، باول (2020). "الهيمنة المعتمدة" . مجلة AKCE الدولية للرسوم البيانية والتوافقيات . 17 (1): 86-97 . دوى : 10.1016/j.akcej.2018.09.004 . ISSN 0972-8600 . 
• دومكي، غايلا س.؛ هاتينغ، يوهانس هـ.؛ هيديتنييمي، ستيفن ت.؛ لاسكار، رينو س.؛ ماركوس، ليزا ر. (1999). "الهيمنة المقيدة في الرسوم البيانية". الرياضيات المتقطعة . 203 ( 1-3 ): 61-69 . doi : 10.1016/S0012-365X(99)00016-3 . ISSN 0012-365X . 
• إسكوفيه، برونو؛ باشوس، فانجيليس ث. (2006)، "الشمولية في فئات التقريب التي تتجاوز APX" (ملف PDF) ، علوم الحاسوب النظرية ، 359 ( 1-3 ): 369-377 ، doi : 10.1016/j.tcs.2006.05.023
• فودري، رالف ؛ فلاندري، إيفلين؛ رياتشيك، زدينيك (1997)، "الرسوم البيانية الخالية من المخالب - دراسة استقصائية"، الرياضيات المتقطعة ، 164 ( 1-3 ): 87-147 ، doi : 10.1016/S0012-365X(96)00045-3 ، MR 1432221 .
• فومين، فيدور ف.؛ غراندوني، فابريزيو؛ كراتش، ديتر (2009)، "نهج القياس والتغلب لتحليل الخوارزميات الدقيقة"، مجلة ACM ، 56 (5): 25:1–32، doi : 10.1145/1552285.1552286 ، S2CID 1186651 .
• فومين، فيدور ف.؛ غراندوني، فابريزيو؛ بياتكين، أرتيم؛ ستيبانوف، أليكسي (2008)، "الحدود التوافقية عبر القياس والغزو: تحديد مجموعات الهيمنة الدنيا وتطبيقاتها"، معاملات ACM في الخوارزميات ، 5 (1): 9:1–17، doi : 10.1145/1435375.1435384 ، S2CID 2489447 .
• فومين، فيدور ف.؛ ثيليكوس، ديميتريوس م. (2006)، "المجموعات المهيمنة في الرسوم البيانية المستوية: عرض الفرع والتسريع الأسي"، مجلة SIAM للحوسبة ، 36 (2): 281، doi : 10.1137/S0097539702419649 ، hdl : 2117/97398 ، S2CID 5232238 .
• فورستر، كلاوس-تيكو. (2013)، "تقريب الهيمنة المتسامحة مع الأخطاء في الرسوم البيانية العامة"، وقائع ورشة العمل العاشرة حول الخوارزميات التحليلية والتوافقية ANALCO ، SIAM، الصفحات 25-32 ، doi : 10.1137/1.9781611973037.4 ، ISBN  978-1-61197-254-2.
• غاري، مايكل ر .؛ جونسون، ديفيد س. (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . سلسلة كتب في العلوم الرياضية (  الطبعة الأولى). نيويورك: دبليو إتش فريمان وشركاه . ISBN 9780716710455MR 0519066 . OCLC 247570676 .​  ، ص  190، المسألة GT2.
• هاس، روث؛ ويكسلر، توماس ب. (2004). "أعداد الهيمنة الموقعة للرسم البياني ومكمله". الرياضيات المتقطعة . 283 ( 1-3 ): 87-92 . doi : 10.1016/j.disc.2004.01.007 . ISSN 0012-365X . 
• هاينز، تيريزا دبليو؛ هيديتنييمي، ستيفن تي؛ سلاتر، بيتر جيه (1998). أساسيات الهيمنة في الرسوم البيانية . مارسيل ديكر. ص 261-262 . ISBN  9780429157769.
• هاينز، تيريزا دبليو؛ سلاتر، بيتر جيه (1998). "الهيمنة الزوجية في الرسوم البيانية". الشبكات . 32 (3): 199-206 . doi : 10.1002/(SICI)1097-0037(199810)32:3 < 199::AID-NET4 > 3.0.CO ; 2-F . ISSN 0028-3045 . 
• هيديتنييمي، إس تي؛ لاسكار، آر سي (1990)، "ببليوغرافيا حول الهيمنة في الرسوم البيانية وبعض التعريفات الأساسية لمعاملات الهيمنة"، الرياضيات المتقطعة ، 86 ( 1-3 ): 257-277 ، doi : 10.1016/0012-365X(90)90365-O.
• كانغ، ل.؛ شان، إ. (2020). "الدوال المهيمنة ذات الإشارة والدوال المهيمنة السالبة في الرسوم البيانية". في: هاينز، ت. و.؛ هيديتنييمي، س. ت.؛ هينينغ، م. أ. (محررون). موضوعات في الهيمنة في الرسوم البيانية . تطورات في الرياضيات. المجلد  64. تشام: سبرينغر. doi : 10.1007/978-3-030-51117-3_9 . ISBN 978-3-030-51117-3.
• كان، فيجو (1992)، حول إمكانية تقريب مسائل التحسين الكاملة من فئة NP (ملف PDF) . أطروحة دكتوراه، قسم التحليل العددي وعلوم الحاسوب، المعهد الملكي للتكنولوجيا ، ستوكهولم{{citation}}: CS1 maint: postscript ( link ) .
• كلاسينغ، رالف؛ لافوريست، كريستيان (2004)، "نتائج الصعوبة وخوارزميات التقريب لهيمنة k-tuple في الرسوم البيانية"، رسائل معالجة المعلومات ، 89 (2): 75-83 ، doi : 10.1016/j.ipl.2003.10.004.
• ماهاديفان، جي؛ أفادايابان، إس؛ جوزيف، جيه بي؛ سوبرامانيان، تي (2012). "عدد الهيمنة الثلاثية المتصلة للرسم البياني". المجلة الدولية للتوافقية الرياضية . 3 : 93-104 .
• مروان، حسين بومدين؛ شلالي، مصطفى (2015). "حول الهيمنة الآمنة في الرسوم البيانية". رسائل معالجة المعلومات . 115 (10): 786-790 . doi : 10.1016/j.ipl.2015.05.006 . ISSN 0020-0190 . 
• ميشولام، روي (1 مايو 2003). "أعداد الهيمنة والتماثل" . مجلة نظرية التوافيق، السلسلة أ . 102 (2): 321-330 . doi : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165 . 
• باباديميتريو، كريستوس هـ.؛ ياناكاكيس، ميهايليس (1991)، "التحسين، والتقريب، وفئات التعقيد"، مجلة علوم الحاسوب والنظم ، 43 (3): 425-440 ، doi : 10.1016/0022-0000(91)90023-X
• باريك، أبهاي ك. (1991)، "تحليل خوارزمية جشعة لإيجاد مجموعات مهيمنة صغيرة في الرسوم البيانية"، رسائل معالجة المعلومات ، 39 (5): 237-240 ، doi : 10.1016/0020-0190(91)90021-9 ، hdl : 1721.1/1201
• راز، ر .؛ صفرا، س. (1997)، "اختبار منخفض الدرجة باحتمالية خطأ شبه ثابتة، وتوصيف PCP لـ NP باحتمالية خطأ شبه ثابتة"، وقائع الندوة السنوية التاسعة والعشرين لجمعية ACM حول نظرية الحوسبة ، ACM، ص 475-484 ، doi : 10.1145/258533.258641 ، ISBN  0-89791-888-6، S2CID 15457604 .
• سامباثكومار، إي. (1989). "عدد الهيمنة العالمية للرسم البياني" . مجلة العلوم الرياضية والفيزيائية . 23 (5): 377-385 .
• تاكاميزاوا، ك.؛ نيشيزيكي، ت .؛ سايتو، ن. (1982)، "قابلية الحساب الخطي للمسائل التوافقية على الرسوم البيانية المتسلسلة المتوازية"، مجلة ACM ، 29 (3): 623-641 ، doi : 10.1145/322326.322328 ، S2CID 16082154 .
• تيل، جان آرني؛ فيلانجر، ينجفي (2012)، "خوارزميات FPT للهيمنة في الرسوم البيانية الخالية من الثنائيات"، في إبستين، ليا؛ فيراجينا، باولو (محرران)، الخوارزميات - ESA 2012: الندوة الأوروبية السنوية العشرون، ليوبليانا، سلوفينيا، 10-12 سبتمبر 2012، وقائع ، سلسلة محاضرات في علوم الحاسوب ، المجلد  7501، سبرينغر، الصفحات 802-812 ، doi : 10.1007/978-3-642-33090-2_69 ، ISBN  978-3-642-33089-6.
• فان رويج، JMM؛ نيدرلوف، J .؛ فان ديك، TC (2009)، “الشمول/الاستبعاد يلتقي بالقياس والقهر: الخوارزميات الدقيقة لحساب المجموعات المهيمنة”، Proc. الندوة الأوروبية السنوية السابعة عشر حول الخوارزميات، ESA 2009 ، ملاحظات محاضرة في علوم الكمبيوتر، المجلد.  5757، سبرينغر، ص 554-565 ، دوى : 10.1007 / 978-3-642-04128-0_50 ، ISBN  978-3-642-04127-3.

• غراندوني، ف. (2006)، "ملاحظة حول تعقيد مجموعة الهيمنة الدنيا"، مجلة الخوارزميات المنفصلة ، ​​4 (2): 209-214 ، CiteSeerX 10.1.1.108.3223 ، doi : 10.1016/j.jda.2005.03.002 .
• غوها، س.؛ خولر، س. (1998)، "خوارزميات التقريب للمجموعات المهيمنة المتصلة" (ملف PDF) ، Algorithmica ، 20 (4): 374-387 ، doi : 10.1007/PL00009201 ، hdl : 1903/830 ، S2CID 1249122 .
• هاينز، تيريزا دبليو ؛ هيديتنييمي، ستيفن؛ سلاتر، بيتر (1998أ)، أساسيات الهيمنة في الرسوم البيانية ، مارسيل ديكر، ISBN 0-8247-0033-3OCLC 37903553​ .
• هاينز، تيريزا دبليو ؛ هيديتنييمي، ستيفن؛ سلاتر، بيتر (1998ب)، الهيمنة في الرسوم البيانية: مواضيع متقدمة ، مارسيل ديكر، ISBN 0-8247-0034-1OCLC 38201061​ .
• ويست، دوغلاس ب. (2001)، مقدمة في نظرية الرسوم البيانية (  الطبعة الثانية)، بيرسون للتعليم.