A heuristic algorithm of recognition of isomorphism of graphs

被引：0
作者：
Glibovets N.N. [1 ]
Ivashchenko S.A. [1 ]
机构：
[1] National University Kievo-Mogilyanskaya Akademiya, Kiev
来源：
Cybernetics and Systems Analysis | 2001年 / 37卷 / 1期
关键词：
Graph isomorphism; Heuristic algorithm; Recognition of isomorphism of graphs;
D O I：
10.1023/A:1016632503967
中图分类号：
学科分类号：
摘要：
A heuristic polynomial algorithm is presented, which is used for the recognition of isomorphism of graphs and can be assigned to the group of methods that use local characteristic invariants of graphs. At each step, the behavior of the algorithm depends on information obtained at its previous steps. All the theorems stated are proved for a class of nonoriented graphs. © 2001 Kluwer Academic/Plenum Publishers.
引用
收藏
页码：138 / 143
页数：5
相关论文
共 50 条
  • [31] On the isomorphism problem for Helly circular-arc graphs
    Koebler, Johannes
    Kuhnert, Sebastian
    Verbitsky, Oleg
    INFORMATION AND COMPUTATION, 2016, 247 : 266 - 277
  • [32] Optimal quadratic-lime isomorphism of ordered graphs
    Jiang, XY
    Bunke, H
    PATTERN RECOGNITION, 1999, 32 (07) : 1273 - 1283
  • [33] A Novel Approach for Graph Isomorphism: Handling Large Graphs
    Somkunwar, Rachna
    Vaze, Vinod M.
    2017 2ND IEEE INTERNATIONAL CONFERENCE ON RECENT TRENDS IN ELECTRONICS, INFORMATION & COMMUNICATION TECHNOLOGY (RTEICT), 2017, : 1242 - 1247
  • [34] ISOMORPHISM OF REGULAR NM-GRAPHS OF DEGREE 4
    Donets, G. A.
    Shulinok, G. A.
    CYBERNETICS AND SYSTEMS ANALYSIS, 2006, 42 (01) : 83 - 89
  • [35] A NEW ALGORITHM FOR INDUCED SUBGRAPH ISOMORPHISM
    Al-Saidi, Nadia M. G.
    Rajab, Nuha A.
    Abdul-Rahman, Hayder N.
    UNIVERSITY POLITEHNICA OF BUCHAREST SCIENTIFIC BULLETIN-SERIES A-APPLIED MATHEMATICS AND PHYSICS, 2016, 78 (01): : 171 - 180
  • [36] Graph isomorphism algorithm by perfect matching
    Fukuda, K
    Nakamori, M
    SYSTEM MODELING AND OPTIMIZATION XX, 2003, 130 : 229 - 238
  • [37] A graph isomorphism algorithm using pseudoinverses
    Bennett, JM
    Edwards, JJ
    BIT, 1996, 36 (01): : 41 - 53
  • [38] New exact and heuristic algorithms for graph automorphism group and graph isomorphism
    Stoichev S.D.
    ACM Journal of Experimental Algorithmics, 2019, 24 (01):
  • [39] Induced Minor Free Graphs: Isomorphism and Clique-Width
    Belmonte, Remy
    Otachi, Yota
    Schweitzer, Pascal
    ALGORITHMICA, 2018, 80 (01) : 29 - 47
  • [40] Induced Minor Free Graphs: Isomorphism and Clique-Width
    Rémy Belmonte
    Yota Otachi
    Pascal Schweitzer
    Algorithmica, 2018, 80 : 29 - 47
12345