स्वतंत्र सेट (ग्राफ सिद्धांत)

सामान्यीकृत पीटरसन ग्राफ GP(12,4) के लिए नौ नीले कोने अधिकतम स्वतंत्र सेट बनाते हैं।

ग्राफ सिद्धांत में, एक स्वतंत्र सेट, स्थिर सेट, कोक्लिक या एंटीक्लिक एक ग्राफ (असतत गणित) में वर्टेक्स (ग्राफ सिद्धांत) का एक सेट है, जिनमें से कोई भी आसन्न नहीं है। यानी यह एक सेट है $S$ शीर्षों का ऐसा है कि प्रत्येक दो शीर्षों के लिए $S$, दोनों को जोड़ने वाला कोई किनारा (ग्राफ सिद्धांत) नहीं है। समान रूप से, ग्राफ़ में प्रत्येक किनारे में अधिकतम एक समापन बिंदु होता है $S$. एक सेट स्वतंत्र है अगर और केवल अगर यह ग्राफ के पूरक ग्राफ में एक क्लिक (ग्राफ सिद्धांत) है। एक स्वतंत्र सेट का आकार इसमें शामिल शीर्षों की संख्या है। स्वतंत्र सेटों को आंतरिक रूप से स्थिर सेट भी कहा जाता है, जिनमें से स्थिर सेट छोटा होता है।

एक अधिकतम स्वतंत्र समुच्चय एक स्वतंत्र समुच्चय है जो किसी अन्य स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है।

एक अधिकतम स्वतंत्र सेट किसी दिए गए ग्राफ के लिए सबसे बड़े संभव आकार का एक स्वतंत्र सेट है $G$. इस आकार को की स्वतंत्रता संख्या कहा जाता है$G$और आमतौर पर द्वारा निरूपित किया जाता है $\alpha (G)$. ऐसे समुच्चय को खोजने की अनुकूलन समस्या को अधिकतम स्वतंत्र समुच्चय समस्या कहा जाता है। यह एक मजबूत एनपी-पूर्णता है | दृढ़ता से एनपी-कठिन समस्या है। इस प्रकार, यह संभावना नहीं है कि ग्राफ़ के अधिकतम स्वतंत्र सेट को खोजने के लिए एक कुशल एल्गोरिथम मौजूद है।

प्रत्येक अधिकतम स्वतंत्र समुच्चय भी अधिकतम होता है, लेकिन इसका विलोम निहितार्थ जरूरी नहीं है।

गुण

अन्य ग्राफ़ पैरामीटर्स से संबंध

एक सेट स्वतंत्र है अगर और केवल अगर यह ग्राफ के पूरक ग्राफ में एक क्लिक (ग्राफ सिद्धांत) है, तो दो अवधारणाएं पूरक हैं। वास्तव में, बिना किसी बड़े समूहों के पर्याप्त रूप से बड़े ग्राफ़ में बड़े स्वतंत्र सेट होते हैं, एक विषय जिसे रैमसे सिद्धांत में खोजा गया है।

एक समुच्चय स्वतंत्र होता है यदि और केवल यदि उसका पूरक एक शीर्ष आवरण हो। इसलिए, सबसे बड़े स्वतंत्र सेट के आकार का योग $\alpha (G)$ और न्यूनतम वर्टेक्स कवर का आकार $\beta (G)$ ग्राफ़ में शीर्षों की संख्या के बराबर है।

एक ग्राफ का एक ग्राफ रंगना $G$ स्वतंत्र उपसमुच्चय में इसके शीर्ष सेट के एक सेट के विभाजन के अनुरूप है। इसलिए एक शीर्ष रंग, रंगीन संख्या में आवश्यक रंगों की न्यूनतम संख्या $\chi (G)$, कम से कम शीर्षों की संख्या का भागफल है $G$ और स्वतंत्र संख्या $\alpha (G)$.

एक द्विदलीय ग्राफ में जिसमें कोई अलग-थलग कोने नहीं हैं, अधिकतम स्वतंत्र सेट में कोने की संख्या न्यूनतम किनारे को कवर करने वाले किनारों की संख्या के बराबर होती है; यह कोनिग की प्रमेय (ग्राफ सिद्धांत) है|कोनिग की प्रमेय।

अधिकतम स्वतंत्र सेट

Main article: Maximal independent set

एक स्वतंत्र समुच्चय जो दूसरे स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है, उच्चिष्ठ कहलाता है। इस तरह के सेट हावी सेट होते हैं। प्रत्येक ग्राफ में अधिकतम 3 होते हैं^n/3 अधिकतम स्वतंत्र सेट, लेकिन कई रेखांकन बहुत कम हैं। एन-वर्टेक्स चक्र ग्राफ में अधिकतम स्वतंत्र सेट की संख्या पेरिन संख्या द्वारा दी गई है, और एन-वर्टेक्स पथ ग्राफ में अधिकतम स्वतंत्र सेट की संख्या पडोवन अनुक्रम द्वारा दी गई है। इसलिए, दोनों संख्याएं 1.324718..., प्लास्टिक संख्या की शक्तियों के समानुपाती हैं।

स्वतंत्र सेट ढूँढना

Further information: Clique problem

कंप्यूटर विज्ञान में, स्वतंत्र सेटों से संबंधित कई कम्प्यूटेशनल समस्याओं का अध्ययन किया गया है।

• अधिकतम स्वतंत्र सेट समस्या में, इनपुट एक अप्रत्यक्ष ग्राफ है, और आउटपुट ग्राफ में अधिकतम स्वतंत्र सेट है। यदि एकाधिक अधिकतम स्वतंत्र सेट हैं, तो केवल एक आउटपुट होना चाहिए। इस समस्या को कभी-कभी वर्टेक्स पैकिंग कहा जाता है।
• अधिकतम-भार स्वतंत्र सेट समस्या में, इनपुट एक अप्रत्यक्ष ग्राफ है जिसके शीर्ष पर भार है और आउटपुट अधिकतम कुल भार के साथ एक स्वतंत्र सेट है। अधिकतम स्वतंत्र समुच्चय समस्या वह विशेष स्थिति है जिसमें सभी भार एक होते हैं।
• अधिकतम स्वतंत्र सेट लिस्टिंग समस्या में, इनपुट एक अप्रत्यक्ष ग्राफ है, और आउटपुट इसके सभी अधिकतम स्वतंत्र सेटों की एक सूची है। अधिकतम स्वतंत्र सेट समस्या को अधिकतम स्वतंत्र सेट लिस्टिंग समस्या के लिए सबरूटीन एल्गोरिथम के रूप में उपयोग करके हल किया जा सकता है, क्योंकि अधिकतम स्वतंत्र सेट को सभी अधिकतम स्वतंत्र सेटों में शामिल किया जाना चाहिए।
• स्वतंत्र सेट निर्णय समस्या में, इनपुट एक अप्रत्यक्ष ग्राफ और एक संख्या 'के है, और आउटपुट एक सत्य मूल्य है: सच है अगर ग्राफ में आकार 'के का एक स्वतंत्र सेट होता है, और गलत अन्यथा .

इनमें से पहली तीन समस्याएं व्यावहारिक अनुप्रयोगों में महत्वपूर्ण हैं; स्वतंत्र सेट निर्णय समस्या नहीं है, लेकिन स्वतंत्र सेट से संबंधित समस्याओं के लिए एनपी-पूर्णता के सिद्धांत को लागू करने के लिए आवश्यक है।

अधिकतम स्वतंत्र सेट और अधिकतम समूह

स्वतंत्र सेट समस्या और क्लिक समस्या पूरक हैं: जी में एक समूह जी के पूरक ग्राफ में एक स्वतंत्र सेट है और इसके विपरीत। इसलिए, कई कम्प्यूटेशनल परिणाम किसी भी समस्या के लिए समान रूप से अच्छी तरह से लागू किए जा सकते हैं। उदाहरण के लिए, क्लिक समस्या से संबंधित परिणामों में निम्नलिखित परिणाम होते हैं:

• स्वतंत्र सेट निर्णय समस्या एनपी-पूर्ण है, और इसलिए यह नहीं माना जाता है कि इसे हल करने के लिए एक कुशल एल्गोरिदम है।
• अधिकतम स्वतंत्र समुच्चय समस्या एनपी कठिन है और यह सन्निकटन एल्गोरिथम के लिए भी कठिन है।

मनमाने ग्राफ़ में अधिकतम क्लिक्स और अधिकतम स्वतंत्र सेटों के बीच घनिष्ठ संबंध के बावजूद, ग्राफ़ के विशेष वर्गों तक सीमित होने पर स्वतंत्र सेट और क्लिक की समस्याएं बहुत भिन्न हो सकती हैं। उदाहरण के लिए, सघन ग्राफ़ के लिए (ऐसे ग्राफ़ जिनमें किनारों की संख्या किसी भी सबग्राफ़ में वर्टिकल की संख्या से ज़्यादा से ज़्यादा स्थिर होती है), अधिकतम क्लिक का आकार बंधा हुआ होता है और बिल्कुल रैखिक समय में पाया जा सकता है; हालाँकि, ग्राफ़ के समान वर्गों के लिए, या यहाँ तक कि सीमाबद्ध डिग्री ग्राफ़ के अधिक प्रतिबंधित वर्ग के लिए, अधिकतम स्वतंत्र सेट खोजना SNP (जटिलता) है। MAXSNP-पूर्ण, जिसका अर्थ है कि, कुछ स्थिर c (डिग्री के आधार पर) के लिए यह इष्टतम के सी के एक कारक के भीतर आने वाले अनुमानित समाधान को खोजने के लिए एनपी-कठिन है।

Further information: Clique problem § Finding maximum cliques in arbitrary graphs

सटीक एल्गोरिदम

अधिकतम स्वतंत्र सेट समस्या एनपी-हार्ड है। हालाँकि, इसे O(n) की तुलना में अधिक कुशलता से हल किया जा सकता है² 2ⁿ) समय जो एक भोली-भाली खोज द्वारा दिया जाएगा जो प्रत्येक शीर्ष उपसमुच्चय की जांच करता है और जांचता है कि क्या यह एक स्वतंत्र सेट है।

2017 तक इसे O (1.1996.1) समय में हल किया जा सकता हैⁿ) बहुपद स्थान का उपयोग करके। अधिकतम डिग्री 3 वाले ग्राफ़ तक सीमित होने पर, इसे O(1.0836.0) समय में हल किया जा सकता है^एन). ग्राफ़ के कई वर्गों के लिए, बहुपद समय में एक अधिकतम भार स्वतंत्र सेट पाया जा सकता है। प्रसिद्ध उदाहरण पंजा-मुक्त रेखांकन हैं, P₅- मुक्त रेखांकन और सही रेखांकन। कॉर्डल ग्राफ़ के लिए, रैखिक समय में अधिकतम भार स्वतंत्र सेट पाया जा सकता है।

अधिकतम वजन स्वतंत्र सेट समस्या को हल करने के लिए मॉड्यूलर अपघटन एक अच्छा उपकरण है; कोग्राफ पर लीनियर टाइम एल्गोरिद्म इसका मूल उदाहरण है। एक अन्य महत्वपूर्ण उपकरण क्लिक विभाजक हैं जैसा कि टारजन द्वारा वर्णित है।

कोनिग की प्रमेय (ग्राफ सिद्धांत) | कोनिग की प्रमेय का अर्थ है कि द्विदलीय ग्राफ में द्विदलीय मिलान एल्गोरिदम का उपयोग करके बहुपद समय में अधिकतम स्वतंत्र सेट पाया जा सकता है।

सन्निकटन एल्गोरिदम

सामान्य तौर पर, अधिकतम स्वतंत्र सेट समस्या को बहुपद समय में एक स्थिर कारक के रूप में अनुमानित नहीं किया जा सकता है (जब तक कि पी = एनपी)। वास्तव में, सामान्य रूप से अधिकतम स्वतंत्र सेट एपीएक्स # संबंधित जटिलता वर्ग है | पॉली-एपीएक्स-पूर्ण, जिसका अर्थ है कि यह किसी भी समस्या के रूप में कठिन है जिसे बहुपद कारक के रूप में अनुमानित किया जा सकता है। हालांकि, प्रतिबंधित वर्गों के रेखांकन के लिए कुशल सन्निकटन एल्गोरिदम हैं।

प्लेनर ग्राफ में

प्लानर ग्राफ़ में, अधिकतम स्वतंत्र सेट को बहुपद समय में किसी भी सन्निकटन अनुपात c < 1 के भीतर अनुमानित किया जा सकता है; माइनर (ग्राफ सिद्धांत) लेने के तहत बंद किए गए ग्राफ़ के किसी भी परिवार में समान बहुपद-समय सन्निकटन योजनाएं मौजूद हैं।

बाउंडेड डिग्री ग्राफ़ में

बाउंडेड डिग्री ग्राफ़ में, प्रभावी सन्निकटन एल्गोरिदम को सन्निकटन अनुपात के साथ जाना जाता है जो अधिकतम डिग्री के निश्चित मान के लिए स्थिर होते हैं; उदाहरण के लिए, एक लालची एल्गोरिद्म जो अधिकतम स्वतंत्र सेट बनाता है, प्रत्येक चरण पर, ग्राफ़ में न्यूनतम डिग्री वर्टेक्स चुनकर और उसके पड़ोसियों को हटाकर, अधिकतम डिग्री Δ वाले ग्राफ़ पर (Δ+2)/3 का अनुमानित अनुपात प्राप्त करता है। ऐसे उदाहरणों के लिए सन्निकटन कठोरता सीमा में सिद्ध हुई थी Berman & Karpinski (1999). वास्तव में, 3-रेगुलर 3-एज-कलरेबल ग्राफ़ पर भी मैक्स इंडिपेंडेंट सेट APX|APX-पूर्ण है।

इंटरसेक्शन ग्राफ में

Main article: Interval scheduling

एक अंतराल ग्राफ एक ग्राफ है जिसमें नोड्स 1-आयामी अंतराल (जैसे समय अंतराल) होते हैं और दो अंतरालों के बीच एक किनारा होता है अगर और केवल अगर वे एक दूसरे को काटते हैं। एक अंतराल ग्राफ में एक स्वतंत्र सेट गैर-अतिव्यापी अंतराल का एक सेट है। इंटरवल ग्राफ़ में अधिकतम स्वतंत्र सेट खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, कार्य निर्धारण के संदर्भ में: जॉब का एक सेट दिया गया है जिसे कंप्यूटर पर निष्पादित किया जाना है, जॉब का अधिकतम सेट खोजें जो बिना हस्तक्षेप के निष्पादित किया जा सकता है एक दूसरे के साथ। इस समस्या को जल्द से जल्द समय सीमा पहले शेड्यूलिंग का उपयोग करके बहुपद समय में हल किया जा सकता है।

ज्यामितीय चौराहों के रेखांकन में

Main article: Maximum disjoint set

एक ज्यामितीय प्रतिच्छेदन ग्राफ एक ऐसा ग्राफ है जिसमें नोड्स ज्यामितीय आकार होते हैं और दो आकृतियों के बीच एक किनारा होता है यदि और केवल यदि वे प्रतिच्छेद करते हैं। एक ज्यामितीय चौराहे के ग्राफ में एक स्वतंत्र सेट केवल असंबद्ध (गैर-अतिव्यापी) आकृतियों का एक सेट है। ज्यामितीय चौराहों के ग्राफ़ में अधिकतम स्वतंत्र सेट खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, स्वचालित लेबल प्लेसमेंट के संदर्भ में: मानचित्र में स्थानों का एक सेट दिया गया है, इन स्थानों के निकट असंबद्ध आयताकार लेबल का अधिकतम सेट खोजें।

चौराहा ग्राफ में अधिकतम स्वतंत्र सेट ढूँढना अभी भी एनपी-पूर्ण है, लेकिन सामान्य अधिकतम स्वतंत्र सेट समस्या की तुलना में अनुमानित करना आसान है। एक हालिया सर्वेक्षण के परिचय में पाया जा सकता है Chan & Har-Peled (2012).

डी-पंजे से मुक्त ग्राफ में

एक ग्राफ़ में एक डी-पंजे डी + 1 कोने का एक सेट है, जिनमें से एक (केंद्र) अन्य डी कोने से जुड़ा हुआ है, लेकिन अन्य डी कोने एक दूसरे से जुड़े नहीं हैं। एक डी-क्लॉ-फ्री ग्राफ एक ऐसा ग्राफ है जिसमें डी-क्लॉ सबग्राफ नहीं होता है। एल्गोरिदम पर विचार करें जो एक खाली सेट के साथ शुरू होता है, और जब तक यह किसी मौजूदा शीर्ष के निकट नहीं होता है, तब तक इसमें एक मनमाना वर्टेक्स जोड़ता है। डी-क्लॉ-फ्री ग्राफ़ में, प्रत्येक जोड़ा शीर्ष अधिकतम स्वतंत्र सेट से अधिकांश d-1 शीर्षों पर अमान्य हो जाता है; इसलिए, यह तुच्छ एल्गोरिथम अधिकतम स्वतंत्र सेट के लिए (d-1)-समीक्षा एल्गोरिथम प्राप्त करता है। वास्तव में, बहुत बेहतर सन्निकटन अनुपात प्राप्त करना संभव है:

• न्यूवॉनर एक बहुपद समय एल्गोरिदम प्रस्तुत किया गया है, जो किसी भी निरंतर ε> 0 के लिए, एक (डी/2-1/63,700,992+ε) पाता है - डी-क्लॉ फ्री ग्राफ में अधिकतम वजन स्वतंत्र सेट के लिए सन्निकटन।
• साइगन एक अर्ध-बहुपद समय एल्गोरिथ्म प्रस्तुत किया है, जो किसी भी ε>0 के लिए, (d+ε)/3 सन्निकटन प्राप्त करता है।

अधिकतम स्वतंत्र सेट ढूँढना

Main article: Maximal independent set

एक तुच्छ लालची एल्गोरिथ्म द्वारा बहुपद समय में एक अधिकतम स्वतंत्र सेट खोजने की समस्या को हल किया जा सकता है। सभी अधिकतम स्वतंत्र सेट समय ओ (3) में पाए जा सकते हैं^n/3) = ओ (1.4423^एन).

अनुप्रयोग

अधिकतम स्वतंत्र सेट और इसके पूरक, वर्टेक्स कवर समस्या, कई सैद्धांतिक समस्याओं के कम्प्यूटेशनल जटिलता सिद्धांत को साबित करने में शामिल है। वे वास्तविक विश्व अनुकूलन समस्याओं के लिए उपयोगी मॉडल के रूप में भी काम करते हैं, उदाहरण के लिए संश्लेषित जीव विज्ञान विज्ञान को डिजाइन करने के लिए स्थिर जीन नियामक नेटवर्क की खोज के लिए अधिकतम स्वतंत्र सेट एक उपयोगी मॉडल है।

यह भी देखें

• किनारों का एक स्वतंत्र सेट किनारों का एक सेट होता है, जिसमें किन्हीं भी दो में एक शीर्ष उभयनिष्ठ नहीं होता है। इसे आमतौर पर मिलान (ग्राफ सिद्धांत) कहा जाता है।
• एक शीर्ष रंग स्वतंत्र सेट में शीर्ष सेट का विभाजन है।

संदर्भ

• Baker, Brenda S. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM, 41 (1): 153–180, doi:10.1145/174644.174650, S2CID 9706753.
• Berman, Piotr; Fujito, Toshihiro (1995), "On approximation properties of the Independent set problem for degree 3 graphs", Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 955, Springer-Verlag, pp. 449–460, doi:10.1007/3-540-60220-8_84, ISBN 978-3-540-60220-0.
• Berman, Piotr; Karpinski, Marek (1999), "On some tighter inapproximability results", Automata, Languages and Programming, 26th International Colloquium, ICALP'99 Prague, Lecture Notes in Computer Science, vol. 1644, Prague: Springer-Verlag, pp. 200–209, doi:10.1007/3-540-48523-6, ISBN 978-3-540-66224-2, S2CID 23288736
• Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis Th.; van Rooij, Johan M. M. (2010), "A bottom-up method and fast algorithms for MAX INDEPENDENT SET", Algorithm theory—SWAT 2010, Lecture Notes in Computer Science, vol. 6139, Berlin: Springer, pp. 62–73, Bibcode:2010LNCS.6139...62B, doi:10.1007/978-3-642-13731-0_7, ISBN 978-3-642-13730-3, MR 2678485.
• Chan, T. M. (2003), "Polynomial-time approximation schemes for packing and piercing fat objects", Journal of Algorithms, 46 (2): 178–189, CiteSeerX 10.1.1.21.5344, doi:10.1016/s0196-6774(02)00294-8.
• Chan, T. M.; Har-Peled, S. (2012), "Approximation algorithms for maximum independent set of pseudo-disks", Discrete & Computational Geometry, 48 (2): 373, arXiv:1103.1431, CiteSeerX 10.1.1.219.2131, doi:10.1007/s00454-012-9417-5, S2CID 38183751.
• Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017.
• Erlebach, T.; Jansen, K.; Seidel, E. (2005), "Polynomial-Time Approximation Schemes for Geometric Intersection Graphs", SIAM Journal on Computing, 34 (6): 1302, doi:10.1137/s0097539702402676.
• Faenza, Yuri; Oriolo, Gianpaolo; Stauffer, Gautier (2014), "Solving the Weighted Stable Set Problem in Claw-Free Graphs", Journal of the ACM, 61 (4): 1–41, doi:10.1145/2629600, S2CID 1995056.
• Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), "A measure & conquer approach for the analysis of exact algorithms", Journal of the ACM, 56 (5): 1–32, doi:10.1145/1552285.1552286, S2CID 1186651, article no. 25{{citation}}: CS1 maint: postscript (link).
• Frank, András (1976), "Some polynomial algorithms for certain graphs and hypergraphs", Congressus Numerantium, XV: 211–226.
• Füredi, Zoltán (1987), "The number of maximal independent sets in connected graphs", Journal of Graph Theory, 11 (4): 463–470, doi:10.1002/jgt.3190110403.
• Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, New York: Springer, ISBN 978-0-387-95220-8.
• Grohe, Martin (2003), "Local tree-width, excluded minors, and approximation algorithms", Combinatorica, 23 (4): 613–632, arXiv:math/0001128, doi:10.1007/s00493-003-0037-9, S2CID 11751235.
• Grötschel, M.; Lovász, L.; Schrijver, A. (1988), "9.4 Coloring Perfect Graphs", Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, Springer-Verlag, pp. 296–298, ISBN 978-0-387-13624-0.
• Halldórsson, M. M.; Radhakrishnan, J. (1997), "Greed is good: Approximating independent sets in sparse and bounded-degree graphs", Algorithmica, 18 (1): 145–163, CiteSeerX 10.1.1.145.4523, doi:10.1007/BF02523693, S2CID 4661668.
• Korshunov, A.D. (1974), "Coefficient of Internal Stability", Kibernetika (in українська), 10 (1): 17–28, doi:10.1007/BF01069014, S2CID 120343511.
• Lokshtanov, D.; Vatshelle, M.; Villanger, Y. (2014), "Independent sets in P₅-free graphs in polynomial time", SODA (Symposium on Discrete Algorithms): 570–581.
• Luby, Michael (1986), "A simple parallel algorithm for the maximal independent set problem", SIAM Journal on Computing, 15 (4): 1036–1053, CiteSeerX 10.1.1.225.5475, doi:10.1137/0215074, MR 0861369.
• Minty, G.J. (1980), "On maximal independent sets of vertices in claw-free graphs", Journal of Combinatorial Theory, Series B, 28 (3): 284–304, doi:10.1016/0095-8956(80)90074-x.
• Moon, J.W.; Moser, Leo (1965), "On cliques in graphs", Israel Journal of Mathematics, 3 (1): 23–28, doi:10.1007/BF02760024, MR 0182577, S2CID 9855414.
• Nakamura, D.; Tamura, A. (2001), "A revision of Minty's algorithm for finding a maximum weight stable set in a claw-free graph", Journal of Operations Research Society Japan, 44 (2): 194–204, doi:10.15807/jorsj.44.194.
• Nobili, P.; Sassano, A. (2015), An O(n^2 log n) algorithm for the weighted stable set problem in claw-free graphs, arXiv:1501.05775, Bibcode:2015arXiv150105775N
• Robson, J. M. (1986), "Algorithms for maximum independent sets", Journal of Algorithms, 7 (3): 425–440, doi:10.1016/0196-6774(86)90032-5.
• Sbihi, Najiba (1980), "Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile", Discrete Mathematics (in français), 29 (1): 53–76, doi:10.1016/0012-365X(90)90287-R, MR 0553650.
• Xiao, Mingyu; Nagamochi, Hiroshi (2017), "Exact algorithms for maximum independent set", Information and Computation, 255: 126–146, arXiv:1312.6260, doi:10.1016/j.ic.2017.06.001, S2CID 1714739.
• Xiao, Mingyu; Nagamochi, Hiroshi (2013), "Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs", Theoretical Computer Science, 469: 92–104, doi:10.1016/j.tcs.2012.09.022.
• Tarjan, R.E. (1985), "Decomposition by clique separators", Discrete Mathematics, 55 (2): 221–232, doi:10.1016/0012-365x(85)90051-2.

बाहरी संबंध

• Weisstein, Eric W. "Maximal Independent Vertex Set". MathWorld.
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring
• Independent Set and Vertex Cover, Hanan Ayad.