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 条
  • [21] Isomorphism Classification of Infinite Sierpinski Carpet Graphs
    D'Angeli, Daniele
    Donno, Alfredo
    PROCEEDINGS OF THE INTERNATIONAL CONFERENCE OF NUMERICAL ANALYSIS AND APPLIED MATHEMATICS 2014 (ICNAAM-2014), 2015, 1648
  • [22] A FASTER ISOMORPHISM TEST FOR GRAPHS OF SMALL DEGREE
    Grohe, Martin
    Neuen, Daniel
    Schweitzer, Pascal
    SIAM JOURNAL ON COMPUTING, 2023, 52 (06) : 1 - 36
  • [23] A Faster Isomorphism Test for Graphs of Small Degree
    Grohe, Martin
    Neuen, Daniel
    Schweitzer, Pascal
    2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2018, : 89 - 100
  • [24] ON ISOMORPHISM BETWEEN DISTANCE-REGULAR GRAPHS
    Goryainov, S. V.
    SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2014, 11 : 311 - 320
  • [25] ISOMORPHISM OF CHORDAL (6,3) GRAPHS
    BABEL, L
    COMPUTING, 1995, 54 (04) : 303 - 316
  • [26] An efficient parallel recognition algorithm for bipartite-permutation graphs
    Yu, CW
    Chen, GH
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1996, 7 (01) : 3 - 10
  • [27] Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
    Neuen, Daniel
    ACM TRANSACTIONS ON ALGORITHMS, 2024, 20 (03)
  • [28] CONNECTIONS BETWEEN THE GRAPH ISOMORPHISM AND THE NUMBER OF WALKS IN GRAPHS
    Czimmermann, Peter
    APLIMAT 2007 - 6TH INTERNATIONAL CONFERENCE, PT II, 2007, : 79 - 84
  • [29] Testing set proportionality and the Adam isomorphism of circulant graphs
    Coppersmith, Don
    Howgrave-Graham, Nick
    Nguyen, Phong Q.
    Shparlinski, Igor E.
    JOURNAL OF DISCRETE ALGORITHMS, 2006, 4 (02) : 324 - 335
  • [30] On the isomorphism of graphs having some eigenvalues of moderate multiplicity
    Elsaesser, Robert
    Trinker, Horst
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2016, 488 : 377 - 395
12345