ग्राफ समरूपता समस्या

ग्राफ समरूपता समस्या यह निर्धारित करने की कम्प्यूटेशनल समस्या है, कि क्या दो परिमित ग्राफ समरूपता समरूपी हैं।

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

यह समस्या ग्राफ समरूपता समस्या का एक विशेष सन्दर्भ है, जो पूछता है कि, क्या दिए गए ग्राफ जी में एक सबग्राफ है, जो दूसरे को दिए गए ग्राफ एच के लिए समरूप है; इस समस्या को एनपी-पूर्ण के रूप में जाना जाता है। यह सममित समूह पर एबेलियन समूह, गैर-अबेलियन समस्या का एक विशेष सन्दर्भ भी माना जाता है।

छवि पहचान के क्षेत्र में इसे सटीक ग्राफ़ मिलान के रूप में जाना जाता है।

अत्याधुनिक

नवंबर 2015 में, लेज़्लो बाबई ने सभी ग्राफ़ों के लिए एक समय जटिलता अर्ध-बहुपद समय एल्गोरिथ्म की घोषणा की, जो कि चलने वाले समय के साथ है $2^{O((\log n)^{c})}$ कुछ निश्चित के लिए $c>0$. 4 जनवरी, 2017 को, बाबई ने अर्ध-बहुपद दावे को वापस ले लिया और हेराल्ड हेलफगोट ने प्रमाण में एक दोष की खोज के पश्चात एक उप-घातीय समय बद्धता को बताया। 9 जनवरी, 2017 को, बाबई ने सुधार की घोषणा की (19 जनवरी को पूर्ण रूप से प्रकाशित) और अर्ध-बहुपद दावे को बहाल किया, साथ ही हेलफगॉट ने फिक्स की पुष्टि की। हेलफगोट आगे दावा करता है कि, c = 3 कोई भी ले सकता है, इसलिए चलने का समय है 2^{O((log n)3)} है।

इससे पूर्व, सबसे अच्छा वर्तमान में स्वीकृत सैद्धांतिक एल्गोरिथम बाबई & लुक्स (1983) के कारण था, और यह लुक्स (1982) के पहले कार्य पर आधारित है, जो वी. एन. ज़ेमल्याचेंको (ज़ेम्लियाचेंको, कोर्नीनको & टायीशकेविच 1985) के सबफैक्टोरियल एल्गोरिथम के साथ संयुक्त है। एल्गोरिथम का रन टाइम 2 है, ^{(√n log n)} n शीर्षों वाले ग्राफ़ के लिए और परिमित सरल समूहों के वर्गीकरण पर निर्भर करता है। इस वर्गीकरण में प्रमेय के अतिरिक्त, थोड़ा कमजोर बंधन होता है।

2O(√n log2 n) द्वारा सबसे पहले लेज़्लो बाबई (1980) द्वारा दृढ़ता से नियमित ग्राफ के लिए प्राप्त किया गया था, और उसके पश्चात बाबई & लुक्स (1983) द्वारा सामान्य ग्राफ तक बढ़ाया गया,घातांक में सुधार √n एक प्रमुख खुली समस्या है; दृढ़ता से नियमित ग्राफ के लिए यह स्पीलमैन (1996) द्वारा किया गया था। बाउंडेड रैंक के हाइपरग्राफ के लिए, बाबई और कोडनोटी (2008) द्वारा ग्राफ़ के विषय से मेल खाने वाली एक उप-घातीय ऊपरी सीमा प्राप्त की गई थी।

ग्राफ समरूपता के लिए कई प्रतिस्पर्धी व्यावहारिक एल्गोरिदम हैं, जैसे कि मैकके (1981), श्मिट और ड्रफेल (1976), उल्मैन (1976), और स्टोइचेव (2019) के कारण। जबकि वे यादृच्छिक ग्राफ पर अच्छा प्रदर्शन करते दिखते हैं, इन एल्गोरिदम का एक बड़ा दोष सबसे निम्न स्थिति में उनका घातीय समय प्रदर्शन है।

ग्राफ समरूपता समस्या संगणनात्मक रूप से एक ग्राफ के स्वसमाकृतिकता समूह की गणना करने की समस्या के समान है, [16] [17] और क्रमपरिवर्तन समूह समरूपता समस्या और क्रमचय समूह प्रतिच्छेद की समस्या से कमजोर है। पश्चात की दो समस्याओं के लिए, बाबई, कांटोर और लुक्स (1983) ने ग्राफ समरूपता के समान जटिलता सीमाएँ प्राप्त कीं।

हल किए गए विशेष विषय

ग्राफ समरूपता समस्या के कई महत्वपूर्ण विशेष विषयों में कुशल, बहुपद-समय का समाधान हैं:

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

जटिलता वर्ग जीआई

चूंकि ग्राफ समरूपता समस्या न तो एनपी-पूर्ण होने के लिए जानी जाती है, और न ही लचीला होने के लिए जानी जाती है, शोधकर्ताओं ने एक नई कक्षा जीआई को परिभाषित करके समस्या में अंतर्दृष्टि प्राप्त करने की मांग की है, ग्राफ समरूपता में बहुपद-समय ट्यूरिंग कमी के साथ समस्याओं का समुच्चय संकट। यदि वास्तव में ग्राफ समरूपता समस्या बहुपद समय में हल करने योग्य है, तो जीआई पी (जटिलता) के समान होगा। दूसरी ओर, यदि समस्या एनपी-पूर्ण है, तो जीआई एनपी (जटिलता) के समान होगा और एनपी में सभी समस्याएं अर्ध-बहुपद समय में हल करने योग्य होंगी।

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

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

जीआई-पूर्ण और जीआई-हार्ड समस्याएं

अन्य वस्तुओं की समरूपता

गणितीय वस्तुओं के कई वर्ग हैं जिनके लिए समरूपता की समस्या एक जीआई-पूर्ण समस्या है। उनमें से कई अतिरिक्त गुणों या प्रतिबंधों से संपन्न ग्राफ़ हैं:

• निर्देशित ग्राफ* लेबल वाले ग्राफ़, इस प्रावधान के साथ कि लेबल को संरक्षित करने के लिए एक समरूपता की आवश्यकता नहीं है,परन्तु केवल समान लेबल वाले शीर्षों के युग्मों वाला तुल्यता संबंध
• ध्रुवीकृत ग्राफ (एक पूर्ण ग्राफ K से बना है_m और एक खाली ग्राफ K_n साथ ही दोनों को जोड़ने वाले कुछ किनारे; उनके समरूपता को विभाजन को बनाए रखना चाहिए)* 2-रंगीन ग्राफ* स्पष्ट रूप से दी गई परिमित संरचना (गणितीय तर्क)।* मल्टीग्राफ* हाइपरग्राफ*स्वचालित रूप से समाप्त* मार्कोव निर्णय प्रक्रिया
• क्रमविनिमेय वर्ग 3 निलपोटेंट (अर्थात, xyz = 0 हर तत्व x, y, z) उपसमूह के लिए* रेडिकल पर जीरो स्क्वेयर रेडिकल और संगड़कीय फैक्टर के साथ फिक्स्ड बीजगणितीय रूप से बंद क्षेत्र पर एक परिमित रैंक सहयोगी बीजगणित।
• संदर्भ-मुक्त व्याकरण*संतुलित अपूर्ण ब्लॉक अभिकल्पनाएँ* वर्टेक्स-पहलू घटनाओं द्वारा दर्शाए गए उत्तल पॉलीटॉप के मिश्रित समरूपता को पहचानना।

जीआई - ग्राफ की पूरी कक्षाएं

ग्राफ़ के एक वर्ग को जीआई-पूर्ण कहा जाता है यदि इस उपवर्ग से ग्राफ़ के लिए समरूपता की पहचान एक जीआई-पूर्ण समस्या है। निम्नलिखित वर्ग जीआई-पूर्ण हैं:* जुड़े ग्राफ

• व्यास के ग्राफ (ग्राफ सिद्धांत) 2 और त्रिज्या (ग्राफ सिद्धांत) 1* निर्देशित विश्वकोश ग्राफ
• नियमित ग्राफ
• गैर-तुच्छ दृढ़ता से नियमित ग्राफ के बिना द्विदलीय ग्राफ
• द्विदलीय ऑयलरीय ग्राफ
• द्विदलीय नियमित ग्राफ
• रेखा ग्राफ
• ग्राफ विभाजित करें
• तारकीय ग्राफ
• नियमित स्व-पूरक ग्राफ
• मनमाना आयामों में सामान्य, सरल पॉलीटोप, और [[साधारण पॉलीटॉप]] उत्तल पॉलीटोप्स के पॉलीटॉपल ग्राफ।

डिग्राफ के कई वर्ग भी जीआई-पूर्ण हैं।

अन्य जीआई-पूर्ण समस्याएं

समरूपता समस्याओं के अलावा अन्य गैर-तुच्छ जीआई-पूर्ण समस्याएं भी हैं।

• किसी ग्राफ या डिग्राफ की आत्म-पूरकता की मान्यता।
• तथाकथित एम-ग्राफ के एक वर्ग के लिए एक क्लिक समस्या। यह दिखाया गया है कि एन-वर्टेक्स ग्राफ के लिए एक समरूपता खोजना आकार एन के एम-ग्राफ में एन-क्लिक खोजने के बराबर है।^{2</उप>। यह तथ्य दिलचस्प है क्योंकि आकार n के एम-ग्राफ में क्रम (1−−ε)n के एक समूह को खोजने की समस्या2 मनमाने ढंग से छोटे सकारात्मक ε के लिए एनपी-पूर्ण है।}
• 2-परिसरों के होमोमोर्फिज्म की समस्या।

जीआई-कठिन समस्याएं

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

प्रोग्राम की जाँच

(मैनुअल ब्लूम & संपथ कन्नन 1995) ने ग्राफ समरूपता के कार्यक्रमों के लिए एक संभाव्य जांचकर्ता प्रदर्शित किया है। मान लीजिए कि पी द्वारा एक दावा किया गया बहुपद-समय प्रक्रिया है, जो जांचता है कि दो ग्राफ संरूपित हैं, परन्तु यह भरोसेमंद नहीं है। यह जाँचने के लिए कि क्या ग्राफ जी और एच तुल्याकारी हैं:

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

यह प्रक्रिया बहुपद-समय है और सही उत्तर देती है यदि पी ग्राफ समरूपता के लिए एक सही कार्यक्रम है। यदि P एक सही प्रोग्राम नहीं है, परन्तु जी और एच पर सही उत्तर देता है, तो जाँचकर्ता या तो सही उत्तर देगा, या पी के अमान्य व्यवहार का पता लगाएगा।

यदि पी एक सही प्रोग्राम नहीं है, और जी और एच पर गलत उत्तर देता है, तो जाँचकर्ता उच्च संभावना के साथ पी के अमान्य व्यवहार का पता लगाएगा, या प्रायिकता 2 के साथ गलत उत्तर देगा।^-100.

विशेष रूप से, पी का उपयोग केवल एक ब्लैक बॉक्स के रूप में किया जाता है।

अनुप्रयोग

ग्राफ़ का उपयोग सामान्यतः कई क्षेत्रों में संरचनात्मक जानकारी को संकेतीकरण करने के लिए किया जाता है, जिसमें संगणक दृष्टि और स्वरूप की पहचान सम्मिलित है, और ग्राफ़ मिलान, अर्थात ग्राफ़ के बीच समानता की पहचान, इन क्षेत्रों में एक महत्वपूर्ण उपकरण है। इन क्षेत्रों में ग्राफ समरूपता समस्या को सटीक ग्राफ मिलान के रूप में जाना जाता है। रासायनिक सूचना विज्ञान और गणितीय रसायन विज्ञान में, रासायनिक डेटाबेस के भीतर एक रासायनिक यौगिक की पहचान करने के लिए ग्राफ समरूपता परीक्षण का उपयोग किया जाता है। इसके अतिरिक्त, कार्बनिक गणितीय रसायन शास्त्र ग्राफ समरूपता परीक्षण में आणविक ग्राफ और संयुक्त रसायन के निर्माण के लिए उपयोगी है।

रासायनिक डेटाबेस खोज चित्रात्मक डेटा माइनिंग का एक उदाहरण है, जहाँ ग्राफ कैनोनाइजेशन दृष्टिकोण का प्रायः उपयोग किया जाता है। विशेष रूप से, रासायनिक पदार्थो के लिए कई पहचानकर्ता, जैसे स्माइल्स और InChI, आणविक जानकारी को संकेतीकरण करने के लिए एक मानक और मानव-पठनीय तरीका प्रदान करने के लिए प्रारूपित किए गए हैं, और डेटाबेस और वेब पर ऐसी जानकारी की खोज को सुविधाजनक बनाने के लिए कैनोनाइजेशन चरण का उपयोग करते हैं। उनकी गणना में, जो अनिवार्य रूप से ग्राफ का कैनोनाइजेशन है जो अणु का प्रतिनिधित्व करता है।

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

यह भी देखें

• ग्राफ ऑटोमोर्फिज्म समस्या
• ग्राफ कैनोनाइजेशन

संदर्भ

• Aho, Alfred V.; Hopcroft, John; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms, Reading, MA: Addison-Wesley.
• Arvind, Vikraman; Köbler, Johannes (2000), "Graph isomorphism is low for ZPP(NP) and other lowness results.", Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 1770, Springer-Verlag, pp. 431–442, doi:10.1007/3-540-46541-3_36, ISBN 3-540-67141-2, MR 1781752.
• Arvind, Vikraman; Kurur, Piyush P. (2006), "Graph isomorphism is in SPP", Information and Computation, 204 (5): 835–852, doi:10.1016/j.ic.2006.02.002, MR 2226371.
• Babai, László (1980), "On the complexity of canonical labeling of strongly regular graphs", SIAM Journal on Computing, 9 (1): 212–216, doi:10.1137/0209018, MR 0557839.
• Babai, László; Codenotti, Paolo (2008), "Isomorphism of hypergraphs of low rank in moderately exponential time" (PDF), Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), IEEE Computer Society, pp. 667–676, doi:10.1109/FOCS.2008.80, ISBN 978-0-7695-3436-7, S2CID 14025744.
• Babai, László; Grigoryev, D. Yu.; Mount, David M. (1982), "Isomorphism of graphs with bounded eigenvalue multiplicity", Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pp. 310–324, doi:10.1145/800070.802206, ISBN 0-89791-070-2, S2CID 12837287.
• Babai, László; Kantor, William; Luks, Eugene (1983), "Computational complexity and the classification of finite simple groups", Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS), pp. 162–171, doi:10.1109/SFCS.1983.10, S2CID 6670135.
• Babai, László; Luks, Eugene M. (1983), "Canonical labeling of graphs", Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), pp. 171–183, doi:10.1145/800061.808746, ISBN 0-89791-099-0, S2CID 12572142.
• Babai, László (2015), Graph Isomorphism in Quasipolynomial Time, arXiv:1512.03547, Bibcode:2015arXiv151203547B
• Baird, H. S.; Cho, Y. E. (1975), "An artwork design verification system", Proceedings of the 12th Design Automation Conference (DAC '75), Piscataway, NJ, USA: IEEE Press, pp. 414–420.
• Blum, Manuel; Kannan, Sampath (1995), "Designing programs that check their work", Journal of the ACM, 42 (1): 269–291, CiteSeerX 10.1.1.38.2537, doi:10.1145/200836.200880, S2CID 52151779.
• Bodlaender, Hans (1990), "Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees", Journal of Algorithms, 11 (4): 631–643, doi:10.1016/0196-6774(90)90013-5, MR 1079454.
• Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report, vol. CS-77-04, Computer Science Department, University of Waterloo.
• Booth, Kellogg S.; Lueker, George S. (1979), "A linear time algorithm for deciding interval graph isomorphism", Journal of the ACM, 26 (2): 183–195, doi:10.1145/322123.322125, MR 0528025, S2CID 18859101.
• Boucher, C.; Loker, D. (2006), Graph isomorphism completeness for perfect graphs and subclasses of perfect graphs (PDF), Technical Report, vol. CS-2006-32, Computer Science Department, University of Waterloo.
• Chung, Fan R. K. (1985), "On the cutwidth and the topological bandwidth of a tree", SIAM Journal on Algebraic and Discrete Methods, 6 (2): 268–277, doi:10.1137/0606026, MR 0778007.
• Colbourn, C. J. (1981), "On testing isomorphism of permutation graphs", Networks, 11: 13–21, doi:10.1002/net.3230110103, MR 0608916.
• Colbourn, Marlene Jones; Colbourn, Charles J. (1978), "Graph isomorphism and self-complementary graphs", ACM SIGACT News, 10 (1): 25–29, doi:10.1145/1008605.1008608, S2CID 35157300.
• Cook, Diane J.; Holder, Lawrence B. (2007), "Section 6.2.1: Canonical Labeling", Mining Graph Data, Wiley, pp. 120–122, ISBN 978-0-470-07303-2.
• Datta, S.; Limaye, N.; Nimbhorkar, P.; Thierauf, T.; Wagner, F. (2009), "Planar graph isomorphism is in log-space", 2009 24th Annual IEEE Conference on Computational Complexity, p. 203, arXiv:0809.2319, doi:10.1109/CCC.2009.16, ISBN 978-0-7695-3717-7, S2CID 14836820.
• Filotti, I. S.; Mayer, Jack N. (1980), "A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus", Proceedings of the 12th Annual ACM Symposium on Theory of Computing, pp. 236–243, doi:10.1145/800141.804671, ISBN 0-89791-017-6, S2CID 16345164.
• Foggia, P.; Sansone, C.; Vento, M. (2001), "A performance comparison of five algorithms for graph isomorphism" (PDF), Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition, pp. 188–199.
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 978-0-7167-1045-5.
• Grigor'ev, D. Ju. (1981), "Complexity of 'wild' matrix problems and of the isomorphism of algebras and graphs", Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta Imeni V. A. Steklova Akademii Nauk SSSR (LOMI) (in Russian), 105: 10–17, 198, MR 0628981{{citation}}: CS1 maint: unrecognized language (link). English translation in Journal of Mathematical Sciences 22 (3): 1285–1289, 1983.
• Hopcroft, John; Wong, J. (1974), "Linear time algorithm for isomorphism of planar graphs", Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 172–184, doi:10.1145/800119.803896, S2CID 15561884.
• Irniger, Christophe-André Mario (2005), Graph Matching: Filtering Databases of Graphs Using Machine Learning, Dissertationen zur künstlichen Intelligenz, vol. 293, AKA, ISBN 1-58603-557-6.
• Kaibel, Volker; Schwartz, Alexander (2003), "On the complexity of polytope isomorphism problems", Graphs and Combinatorics, 19 (2): 215–230, arXiv:math/0106093, doi:10.1007/s00373-002-0503-y, MR 1996205, S2CID 179936, archived from the original on 2015-07-21.
• Kelly, Paul J. (1957), "A congruence theorem for trees", Pacific Journal of Mathematics, 7: 961–968, doi:10.2140/pjm.1957.7.961, MR 0087949.
• Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "Graph isomorphism is low for PP", Computational Complexity, 2 (4): 301–330, doi:10.1007/BF01200427, MR 1215315, S2CID 8542603.
• Kozen, Dexter (1978), "A clique problem equivalent to graph isomorphism", ACM SIGACT News, 10 (2): 50–52, doi:10.1145/990524.990529, S2CID 52835766.
• Luks, Eugene M. (1982), "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences, 25: 42–65, doi:10.1016/0022-0000(82)90009-5, MR 0685360, S2CID 2572728.
• Luks, Eugene M. (1986), "Parallel algorithms for permutation groups and graph isomorphism", Proc. IEEE Symp. Foundations of Computer Science, pp. 292–302.
• Mathon, Rudolf (1979), "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (3): 131–132, doi:10.1016/0020-0190(79)90004-8, MR 0526453.
• McKay, Brendan D. (1981), "Practical graph isomorphism", 10th. Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980), Congressus Numerantium, vol. 30, pp. 45–87, MR 0635936.
• Miller, Gary (1980), "Isomorphism testing for graphs of bounded genus", Proceedings of the 12th Annual ACM Symposium on Theory of Computing, pp. 225–235, doi:10.1145/800141.804670, ISBN 0-89791-017-6, S2CID 13647304.
• Miller, Gary L. (1983), "Isomorphism testing and canonical forms for k-contractable graphs (a generalization of bounded valence and bounded genus)", Proc. Int. Conf. on Foundations of Computer Theory, Lecture Notes in Computer Science, vol. 158, pp. 310–327, doi:10.1007/3-540-12689-9_114. Full paper in Information and Control 56 (1–2): 1–20, 1983.
• Moore, Cristopher; Russell, Alexander; Schulman, Leonard J. (2008), "The symmetric group defies strong Fourier sampling", SIAM Journal on Computing, 37 (6): 1842–1864, arXiv:quant-ph/0501056, doi:10.1137/050644896, MR 2386215, S2CID 9550284.
• Muzychuk, Mikhail (2004), "A Solution of the Isomorphism Problem for Circulant Graphs", Proc. London Math. Soc., 88: 1–41, doi:10.1112/s0024611503014412, MR 2018956, S2CID 16704931.
• Narayanamurthy, S. M.; Ravindran, B. (2008), "On the hardness of finding symmetries in Markov decision processes" (PDF), Proceedings of the Twenty-Fifth International Conference on Machine Learning (ICML 2008), pp. 688–696.
• Schmidt, Douglas C.; Druffel, Larry E. (1976), "A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices", Journal of the ACM, 23 (3): 433–445, doi:10.1145/321958.321963, MR 0411230, S2CID 6163956.
• Schöning, Uwe (1987), "Graph isomorphism is in the low hierarchy", Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, pp. 114–124; also Journal of Computer and System Sciences 37: 312–323, 1988.
• Shawe-Taylor, John; Pisanski, Tomaž (1994), "Homeomorphism of 2-complexes is graph isomorphism complete", SIAM Journal on Computing, 23 (1): 120–132, doi:10.1137/S0097539791198900, MR 1258998.
• Spielman, Daniel A. (1996), "Faster isomorphism testing of strongly regular graphs", Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC '96), ACM, pp. 576–584, ISBN 978-0-89791-785-8.
• Ullman, Julian R. (1976), "An algorithm for subgraph isomorphism" (PDF), Journal of the ACM, 23: 31–42, CiteSeerX 10.1.1.361.7741, doi:10.1145/321921.321925, MR 0495173, S2CID 17268751.

सर्वेक्षण और मोनोग्राफ

• Read, Ronald C.; Corneil, Derek G. (1977), "The graph isomorphism disease", Journal of Graph Theory, 1 (4): 339–363, doi:10.1002/jgt.3190010410, MR 0485586.
• Gati, G. (1979), "Further annotated bibliography on the isomorphism disease", Journal of Graph Theory, 3 (2): 95–109, doi:10.1002/jgt.3190030202.
• Zemlyachenko, V. N.; Korneenko, N. M.; Tyshkevich, R. I. (1985), "Graph isomorphism problem", Journal of Mathematical Sciences, 29 (4): 1426–1481, doi:10.1007/BF02104746, S2CID 121818465. (Zapiski Nauchnykh Seminarov Leningradskogo विभाग के Matematicheskogo Instituta im. V. A. Steklova AN SSSR से अनुवादित (यूएसएसआर एकेडमी ऑफ साइंसेज के स्टेक्लोव इंस्टीट्यूट ऑफ मैथमेटिक्स के लेनिनग्राद विभाग के सेमिनारों का रिकॉर्ड), वॉल्यूम 118, पीपी। 83-158, 1982। )
• Arvind, V.; Torán, Jacobo (2005), "Isomorphism testing: Perspectives and open problems" (PDF), Bulletin of the European Association for Theoretical Computer Science, 86: 66–84. (ग्राफ, रिंग और समूहों के लिए समरूपता समस्या से संबंधित मुक्त प्रश्नों का एक संक्षिप्त सर्वेक्षण।)
• Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, ISBN 978-0-8176-3680-7. (बुक कवर से: पुस्तकें समस्या की कम्प्यूटेशनल जटिलता के मुद्दे पर ध्यान केंद्रित करती हैं और कई हालिया परिणाम प्रस्तुत करती हैं जो कक्षा एनपी के साथ-साथ अन्य जटिलता वर्गों में समस्या की सापेक्ष स्थिति की बेहतर समझ प्रदान करती हैं।)
• Johnson, David S. (2005), "The NP-Completeness Column", ACM Transactions on Algorithms, 1 (1): 160–176, doi:10.1145/1077464.1077476, S2CID 12604799. (कॉलम का यह 24वां संस्करण विशेष रूप से ग्राफ आइसोमोर्फिज्म के लिए कंप्यूटर और इंट्रेक्टेबिलिटी और पिछले कॉलम से खुली समस्याओं के लिए कला की स्थिति पर चर्चा करता है।)
• Torán, Jacobo; Wagner, Fabian (2009), "The complexity of planar graph isomorphism" (PDF), Bulletin of the European Association for Theoretical Computer Science, 97, archived from the original (PDF) on 2010-09-20, retrieved 2010-06-03.
• Stoichev, Stoicho D. (2019), "New Exact and Heuristic Algorithms for Graph Automorphism Group and Graph Isomorphism", Journal of Experimental Algorithmics, 24: 1–27, doi:10.1145/3333250, S2CID 202676274.

सॉफ्टवेयर

• ग्राफ समरूपता, कार्यान्वयन की समीक्षा, द स्टोनी ब्रुक एल्गोरिथम रिपॉजिटरी।

श्रेणी:ग्राफ़ एल्गोरिदम श्रेणी:रूपवाद श्रेणी:ग्राफ़ थ्योरी में कम्प्यूटेशनल समस्याएं श्रेणी:कंप्यूटर विज्ञान में अनसुलझी समस्याएं श्रेणी:कम्प्यूटेशनल जटिलता सिद्धांत