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

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

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

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

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

अत्याधुनिक

नवंबर 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), और उसके बाद सामान्य रेखांकन तक बढ़ाया गया Babai & Luks (1983). प्रतिपादक में सुधार √n एक बड़ी खुली समस्या है; जोरदार नियमित रेखांकन के लिए यह द्वारा किया गया था, स्पीलमैन (1996).बाउंडेड रैंक के hypergraph के लिए, ग्राफ के मामले से मेल खाने वाली एक सब-एक्सपोनेंशियल टाइम अपर बाउंड द्वारा प्राप्त किया गया था बाबई & कोडेनोट्टी (2008).

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

ग्राफ़ समरूपता समस्या कम्प्यूटेशनल रूप से ग्राफ़ के ऑटोमोर्फिज़्म समूह की गणना करने की समस्या के समतुल्य है, <रेफ नाम = लुक्स पीपी। 139-175 >Luks, Eugene (1993-09-01). "Permutation groups and polynomial-time computation". असतत गणित और सैद्धांतिक कंप्यूटर विज्ञान में DIMACS श्रृंखला. Vol. 11. Providence, Rhode Island: American Mathematical Society. pp. 139–175. doi:10.1090/dimacs/011/11. ISBN 978-0-8218-6599-6. ISSN 1052-1798.</ref> और क्रमचय समूह समरूपता समस्या और क्रमचय समूह प्रतिच्छेदन समस्या से कमजोर है। बाद की दो समस्याओं के लिए, Babai, Kantor & Luks (1983) ग्राफ आइसोमोर्फिज्म के समान जटिलता सीमा प्राप्त की।

हल किए गए विशेष मामले

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

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

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

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

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

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

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

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

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

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

जीआई - रेखांकन की पूरी कक्षाएं

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

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

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

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

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

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

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

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

प्रोग्राम चेकिंग

Manuel Blum and Sampath Kannan (1995) ने ग्राफ समरूपता के कार्यक्रमों के लिए एक संभाव्य जांचकर्ता दिखाया है। मान लीजिए कि पी एक दावा किया गया बहुपद-समय प्रक्रिया है जो जांचता है कि दो ग्राफ आइसोमोर्फिक हैं, लेकिन यह भरोसेमंद नहीं है। यह जाँचने के लिए कि क्या रेखांकन G और H तुल्याकारी हैं:

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

यह प्रक्रिया बहुपद-समय है और सही उत्तर देती है यदि पी ग्राफ समरूपता के लिए एक सही कार्यक्रम है। यदि P एक सही प्रोग्राम नहीं है, लेकिन G और H पर सही उत्तर देता है, तो चेकर या तो सही उत्तर देगा, या P के अमान्य व्यवहार का पता लगाएगा। यदि P एक सही प्रोग्राम नहीं है, और G और H पर गलत उत्तर देता है, तो चेकर उच्च संभावना के साथ P के अमान्य व्यवहार का पता लगाएगा, या प्रायिकता 2 के साथ गलत उत्तर देगा।^-100.

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

अनुप्रयोग

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

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

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

यह भी देखें

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

संदर्भ

• 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.

सॉफ्टवेयर

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

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