그래프 이형성 문제
Graph isomorphism problem
그래프 이형성 문제는 두 개의 유한 그래프가 이형성인지 여부를 결정하는 연산 문제다.
이 문제는 다항식 시간에는 해결할 수 없고 NP-완전한 것으로 알려져 있지 않기 때문에 계산 복잡도 등급 NP-중간에 있을 수 있다.그래프 이형성 문제는 NP 등급의 낮은 계층 구조에 있는 것으로 알려져 있는데, 이는 다항식 시간 계층이 2단계로 무너지지 않는 한 NP 완전성이 아님을 시사한다.[1]동시에, 많은 특별한 등급의 그래프의 이소모르퍼시즘은 다항식 시간에 해결될 수 있고, 실제로 그래프의 이소모르퍼시즘은 효율적으로 해결될 수 있는 경우가 많다.[2][3]
이 문제는 서브그래프 이형성 문제의 특별한 경우로서,[4] 주어진 그래프 G가 다른 주어진 그래프 H에 대해 이형성이 있는 서브그래프를 포함하고 있는지 여부를 묻는 것이다. 이 문제는 NP-완전한 것으로 알려져 있다.또한 대칭군에 대한 비아벨리안 숨겨진 부분군 문제의 특수한 경우라고 알려져 있다.[5]
이미지 인식 영역에서는 정확한 그래프 일치로 알려져 있다.[6]
예술 상태
11월 2015년에, 라슬로 Babai 2O((통나무 n)c){\displaystyle 2^{O((\log n)^{c}상영 시간)}}와 함께 고정 c>;1월 4일 2017년에 0{\displaystyle c>0}.[7][8][9][10], Babai고 sub-expone 말했다quasi-polynomial 주장 철회 모두 그래프에 대한quasipolynomial 시간 알고리즘, 그 하나이다, 발표했다.ntial 시간에 묶여하랄드 헬프고트가 증거의 결함을 발견한 후로는 변하지 않았다.2017년 1월 9일 바바이는 정정(완전 1월 19일 발행)을 발표하고 준폴리네임 주장을 복원했으며, 힐프고트가 수정안을 확정했다.[11][12]헬프곶은 c = 3을 가져갈 수 있다고 주장하기 때문에 러닝 타임이 2이다O((log n)3).[13][14]
이에 앞서 현재 가장 잘 수용되고 있는 이론 알고리즘은 바바이 & 루크(1983) 때문이었으며, 루크(1982)가 V. N. 제밀야첸코(Zemyachenko, Korneenko & Tyshkevich 1985)의 하위요소 알고리즘과 결합한 초기 연구에 바탕을 두고 있다.알고리즘은 정점이 없는 그래프에 대해 런타임O(√n log n) 2를 가지며 유한 단순 그룹의 분류에 의존한다.이 분류 정리가 없다면, 먼저 라슬로 바바이(1980년)가 강력하게 규칙적인 그래프에 대해 약간 약한 바운드 2를O(√n log2 n) 얻은 다음, 바바이 & 루크스(1983)가 일반 그래프까지 확장했다.지수 improvementn의 개선은 중요한 개방적인 문제인데, 강력한 정규 그래프의 경우 이것은 스필먼(1996)에 의해 이루어졌다.경계 등급의 하이퍼그래프의 경우, 그래프의 사례와 일치하는 하위 항목 상한을 Babai & Codenotti(2008)에 의해 얻었다.
그래프 이형성을 위한 몇 가지 경쟁적인 실제 알고리즘이 있는데, 예를 들어 맥케이(1981), 슈미트 & 드루펠(1976), 울만(1976)에 기인한다.무작위 그래프에서는 성능이 좋은 것처럼 보이지만, 이러한 알고리즘의 주요 단점은 최악의 경우 기하급수적인 시간 성능이다.[15]
그래프 이형성 문제는 그래프의 자동성 그룹을 계산하는 문제와 연산적으로 동등하며 순열성 이형성 문제, 순열성 그룹 교차로 문제보다 약하다.[16][17]후자의 두 문제에 대해, 바바이, 칸토르 & 루크(1983)는 그래프 이형성의 경우와 유사한 복잡도 한계를 얻었다.
해결된 특수 사례
그래프 이형성 문제의 많은 중요한 특별한 경우들은 효율적인 다항식 시간 해결책을 가지고 있다.
- 나무들[18][19]
- 평면 그래프[20](사실 평면 그래프 이형성은 로그 공간에 있으며,[21] 클래스는 P에 포함되어 있음)
- 구간 그래프[22]
- 순열 그래프[23]
- 순환 그래프[24]
- 경계 모수 그래프
복잡도 등급 GI
그래프 이형성 문제는 NP-완전한 것으로도 알려져 있지 않고 추적 가능한 것으로 알려져 있지 않기 때문에, 연구자들은 그래프 이형성 문제에 대한 다항 시간 튜링 감소의 일련의 문제인 새로운 등급 GI를 정의함으로써 문제에 대한 통찰력을 얻으려고 노력해왔다.[31]실제로 다항식 시간에 그래프 이형성 문제가 해결 가능하다면 GI는 P와 같을 것이다.반면에, 만약 문제가 NP-완전이라면, GI는 NP와 같을 것이고, NP의 모든 문제는 준-폴리놈 시간 내에 해결할 수 있을 것이다.
다항식 시간 계층 내의 복잡성 등급에서 흔히 그렇듯이, 다항식 시간 튜링 문제가 GI의 어떤 문제에서 그 문제로 감소하는 경우, 즉 GI-하드 문제에 대한 다항식 시간 솔루션이 그래프 이형성 문제(그러므로 GI의 모든 문제)에 다항식 시간 해결책을 산출할 경우 문제를 GI-하드라고 부른다.문제 이(가) GI-hard이고 GI 문제에 대한 다항식 시간 솔루션이 X에 다항식 시간 솔루션을 제공하는 경우 GI 또는 GI-완성에 대해 완료라고 불린다
(가) GI-hard이고 GI 문제에 대한 다항식 시간 솔루션이 그래프 이형성 문제는 NP와 co-AM에 모두 포함되어 있다.GI는 패리티 P에 대해 포함되고 낮으며 잠재적으로 훨씬 더 작은 등급의 SPP에도 포함된다.[32]그것이 패리티 P에 있다는 것은 그래프 이형성 문제가 다항 시간 비결정론적 튜링 기계가 짝수 또는 홀수 수의 승인 경로를 가지고 있는지 여부를 결정하는 것보다 어렵지 않다는 것을 의미한다.ZPP의NP 경우 GI도 포함되고 낮음도 포함된다.[33]이것은 본질적으로 NP 신탁에 접근할 수 있는 효율적인 라스베이거스 알고리즘이 그래프 이형성을 매우 쉽게 해결할 수 있다는 것을 의미하므로 일정한 시간에 그래프를 할 수 있는 능력이 주어지는 것으로부터 힘을 얻지 못한다.
GI 완성 및 GI 하드 문제
다른 물체의 이형성
이형동성의 문제가 GI-완전성 문제인 수학적 객체의 여러 등급이 있다.이러한 그래프 중 일부는 추가 속성 또는 제한이 부여된 그래프들이다.[34]
- 비석[34]
- 라벨이 붙은 그래프, 라벨을 보존하기 위해 이형성이 필요하지 않다는 단서가 있는,[34] 라벨이 같은 정점 쌍으로 구성된 동등성 관계만 있는 그래프
- "양극화된 그래프" (완전한 그래프 K와m 빈 그래프 K와n 둘을 연결하는 일부 가장자리로 만들어졌으며, 이들의 이형성은 칸막이를 보존해야 한다)[34]
- 2색 그래프[34]
- 명시적으로 주어진 유한 구조[34]
- 다문자[34]
- 하이퍼그래프[34]
- 유한 자동자[34]
- 마르코프 의사결정 프로세스[35]
- 정류 클래스 3 nilpotent(즉, 모든 요소에 대해 xyz = 0) 세미그룹[34]
- 고정된 대수학적으로 폐쇄된 분야에 대한 유한 계급 연상 알헤브라의 0 제곱 급진적이고 래디컬에 대한 상호 작용 인자.[34][36]
- 문맥이 없는 문법[34]
- 균형 불완전한 블럭 설계[34]
- 정점-시설 침윤으로 대표되는 볼록 폴리포트의 결합 이형성을 인식한다.[37]
 |
GI 전체 그래프 클래스
이 하위 클래스의 그래프에 대해 이형성을 인식하는 것이 GI-완전성 문제라면 그래프 클래스를 GI-완전성이라고 한다.다음 클래스는 GI 완료:[34]
- 연결된 그래프[34]
- 지름 2 및 반지름 1의[34] 그래프
- 지시된 반복 그래프[34]
- 정규 그래프[34]
- 강력하고 정규적인 하위[34] 그래프가 없는 초당적 그래프
- 초당적 오일러 그래프[34]
- 양분 정규[34] 그래프
- 선 그래프[34]
- 그래프를 분할하다[38]
- 화음 그래프[34]
- 규칙적인 자가 측정 그래프[34]
- 임의 치수의 일반, 단순 및 단순 볼록 폴리토프의 다층 그래프.[39]
|
많은 종류의 디그래프들도 GI-완전하다.
기타 GI 완료 문제
이형성 문제 외에도 다른 비종교적인 GI 완성 문제가 있다.
- 그래프 또는 디그래프의 자기 완성도 인식.[40]
- 소위 M-그래프라고 불리는 계층의 집단 문제.n-vertex 그래프의 이형성을 찾는 것은 n 크기의2 M-그래프에서 n-clik를 찾는 것과 동등하다는 것을 보여준다.이2 사실은 N 사이즈의 M-그래프에서 (n - )) 클라이크를 찾는 문제가 임의로 작은 양의 ε에 대한 NP-완전이기 때문에 흥미롭다.[41]
- 2개 복합체의 동형성 문제.[42]
GI-하드 문제
- 두 그래프 사이에 이형화 수를 세는 문제는 한 그래프라도 존재하는지 여부를 판별하는 문제와 맞먹는 다항시간이다.[43]
- V-설명이나 H-설명 중 하나에 의해 주어지는 볼록한 두 개의 폴리탑이 투영적으로 또는 아순하게 이형인지 여부를 결정하는 문제.후자는 두 개의 폴리토페스를 포함하고 있는 공간 사이에 투영적 또는 아핀 지도가 존재한다는 것을 의미하며, 이는 폴리토페스 사이의 편차를 유도한다.[39]
프로그램 확인
Manuel Blum과 Sampath Kannan(1995)은 그래프 이형성 프로그램에 대한 확률론적 체커를 보여주었다.P가 두 개의 그래프가 이형인지 여부를 확인하는 청구된 다항식 시간 절차라고 가정해 보십시오.그래프 G와 H가 이형인지 확인하려면:
- P에게 G와 H가 이형인지 물어본다.
- 대답이 "예"인 경우:
- P를 서브루틴으로 사용하여 이형성 구조를 시도한다.정점 u를 G, v에 H로 표시하고 그래프를 수정하여 (작은 국소 변경으로) 구별되도록 하십시오.수정된 그래프가 이형인지 P에게 물어보십시오.아니오인 경우 v를 다른 꼭지점으로 변경하십시오.계속 검색하십시오.
- 이형성(異形性)이 발견될 것이다(그리고 검증될 수 있다), 그렇지 않으면 P는 스스로 모순될 것이다.
- "아니오"라고 대답할 경우:
- 다음 작업을 100회 수행하십시오.임의로 G 또는 H를 선택하고 정점을 임의로 허용한다.그래프가 G와 H에 대해 이형성이 있는지 P에게 물어보십시오(그래프의 비이형성에 대한 AM 프로토콜의 경우).
- 테스트 중 하나라도 실패하면 P를 유효하지 않은 프로그램으로 판단한다.그렇지 않으면 "아니오"라고 대답한다.
- 대답이 "예"인 경우:
이 절차는 다항식 시간이며 P가 그래프 이형성에 대한 올바른 프로그램인 경우 정답을 제시한다.P가 올바른 프로그램이 아니라 G와 H에서 정답을 맞추면 체커는 정답을 제시하거나 P의 잘못된 행동을 탐지한다.P가 올바른 프로그램이 아니고 G와 H에서 오답하는 경우, 체커는 확률이 높은 P의 잘못된 행동을 탐지하거나 확률−100 2로 오답한다.
특히 P는 블랙박스로만 쓰인다.
적용들
그래프는 컴퓨터 비전, 패턴 인식 등 여러 분야의 구조 정보를 인코딩하는 데 일반적으로 사용되며, 그래프 매칭, 즉 그래프 간의 유사성 확인은 이러한 영역에서 중요한 도구다.이러한 영역에서 그래프 이형성 문제는 정확한 그래프 일치로 알려져 있다.[44]
척도학 및 수학적 화학에서 그래프 이형성 시험은 화학 데이터베이스 내의 화학 화합물을 식별하는 데 사용된다.[45]또한 유기 수학적 화학 그래프에서 이형성 테스트는 분자 그래프의 생성과 컴퓨터 합성에도 유용하다.
화학 데이터베이스 검색은 그래픽 데이터 마이닝의 한 예로서, 그래프 시성화 접근법이 자주 사용된다.[46]특히 분자 정보를 암호화하고 데이터베이스와 웹에서 그러한 정보의 검색을 용이하게 하기 위해 표준적이고 사람이 읽을 수 있는 방법을 제공하기 위해 고안된 스마일즈, InChi와 같은 화학 물질에 대한 다수의 식별자는 그들의 계산에 시성 단계를 사용하는데, 이것은 근본적으로 그래프의 시성화인 것이다.h는 분자를 나타낸다.
전자 설계 자동화 그래프에서 이형성은 LVS(Layout Bas Schemote) 회로 설계 단계의 기초로서, 회로 도식도와 집적 회로 레이아웃으로 대표되는 전기 회로가 동일한지 여부를 검증하는 것이다.[47]
참고 항목
메모들
- ^ 숄닝(1987년).
- ^ Babai, László; Erdős, Paul; Selkow, Stanley M. (1980-08-01). "Random Graph Isomorphism". SIAM Journal on Computing. 9 (3): 628–635. doi:10.1137/0209047. ISSN 0097-5397.
- ^ 맥케이(1981년).
- ^ 울먼(1976년).
- ^ 무어, 러셀 & 슐만 (2008)
- ^ Endika Bengoetxea, "분포 알고리즘의 추정을 이용한 비작위 그래프 일치", 박사 D, 2002, 2장:그래프 일치 문제(2017년 6월 28일 회수)
- ^ "Mathematician claims breakthrough in complexity theory". Science. November 10, 2015.
- ^ 바바이 (2015년)
- ^ 바바이 홈페이지에서 링크된 2015년 첫 강의 영상
- ^ "The Graph Isomorphism Problem". Communications of the ACM. Retrieved 4 May 2021.
- ^ Babai, László (January 9, 2017), Graph isomorphism update
- ^ Erica Klarreich (January 14, 2017). "Graph Isomorphism Vanquished — Again". Quanta Magazine.
- ^ Helfgott, Harald (January 16, 2017), Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...), arXiv:1701.04372, Bibcode:2017arXiv170104372A
- ^ Dona, Daniele; Bajpai, Jitendra; Helfgott, Harald Andrés (October 12, 2017). "Graph isomorphisms in quasi-polynomial time". arXiv:1710.04574 [math.GR].
- ^ Foggia, Sansone & Vento(2001년).
- ^ Luks, Eugene (1993-09-01). "Permutation groups and polynomial-time computation". DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 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.
- ^ 알제보이(https://cs.stackexchange.com/users/90177/algeboy), Graph Isomorphism and the automorphism group, URL(버전: 2018-09-20): https://cs.stackexchange.com/q/97575
- ^ 켈리(1957년).
- ^ 아호, 홉크로프트 & 울만(1974년), 페이지 84-86.
- ^ 홉크로프트&웡(1974년).
- ^ 다타 외 (2009).
- ^ 부스 앤 루커 (1979년).
- ^ 콜번(1981년).
- ^ 무쯔추크(2004년).
- ^ 보들렌더(1990).
- ^ 밀러 1980; 필로티 & 메이어 1980.
- ^ 루크스(1982년).
- ^ 바바이, 그리고리예프 & 마운트(1982년).
- ^ 밀러(1983년).
- ^ 루크스(1986년).
- ^ Boot & Colbourn 1977; Köbler, Schöning & Toran 1993.
- ^ 쾨블러, 숄닝 & 토란 1992; 아르빈드 & 쿠루르 2006
- ^ 아르빈드&코블러(2000년).
- ^ a b c d e f g h i j k l m n o p q r s t u v w x 젬랴첸코, 코르넨코 & 티슈케비치 (1985년)
- ^ 나라야무르시 & 라빈드란(2008).
- ^ 그리고르예프(1981년).
- ^ 존슨 (2005); 카이벨 & 슈워츠 (2003)
- ^ 정씨(1985년).
- ^ a b 카이벨 & 슈워츠(2003년).
- ^ Colbourn & Colbourn (1978년).
- ^ 코젠(1978년).
- ^ Shawe-Taylor & Pisanski(1994년).
- ^ Mathon (1979년); Johnson 2005.
- ^ Endika Bengoetxea, 박사학위, 추상적
- ^ 이르니거(2005년).
- ^ Cook & Holder(2007)
- ^ 베어드&조(1975년).
참조
- 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광주.(1981년),"'wild의 행렬 문제의 복잡성과 algebras와 그래프의 유질 동상의", Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta Imeni VA.Steklova Akademii Nauk 통신 보안 현황 보고(저 산화 상태 금속 이온)(러시아어로), 105:10–17, 198MR0628981.필기장 수리 과학 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. 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.
- 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.
- 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; 또한 컴퓨터 및 시스템 과학 저널 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. (자피스키 나우슈니크 세미나에서 번역됨) 레닌그라드스코고 오트델레니야 마테마테츠코고 연구소임. V. A. Steklova AN SSSR (구소련의 Steklov 수학 연구소 레닌그라드 학부 세미나 기록), 제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. (책 표지:이 책들은 문제의 계산적 복잡성 문제에 초점을 맞추고 있으며, 다른 복잡성 수업에서뿐만 아니라 클래스 NP에서 문제의 상대적 위치를 더 잘 이해할 수 있는 몇 가지 최근 결과를 제시한다.)
- Johnson, David S. (2005), "The NP-Completeness Column", ACM Transactions on Algorithms, 1 (1): 160–176, doi:10.1145/1077464.1077476, S2CID 12604799(이번 24일자 칼럼에서는 컴퓨터와 난해성 책과 특히 Graph Isomorphism에 관한 이전의 칼럼에서 열린 문제에 대한 예술의 상태를 논하고 있다.)
- 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.
소프트웨어
- 그래프 이형성, 구현 검토, 스토니 브룩 알고리즘 리포지토리.
