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 条
  • [41] Isomorphism for Graphs of Bounded Connected-Path-Distance-Width
    Otachi, Yota
    ALGORITHMS AND COMPUTATION, ISAAC 2012, 2012, 7676 : 455 - 464
  • [42] OPLE: A Heuristic Custom Instruction Selection Algorithm Based on Partitioning and Local Exploration of Application Dataflow Graphs
    Kamal, Mehdi
    Afzali-Kusha, Ali
    Safari, Saeed
    Pedram, Massoud
    ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS, 2015, 14 (04)
  • [43] Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
    Grohe, Martin
    Marx, Daniel
    STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2012, : 173 - 192
  • [44] An Improved Isomorphism Test for Bounded-tree-width Graphs
    Grohe, Martin
    Neuen, Daniel
    Schweitzer, Pascal
    Wiebking, Daniel
    ACM TRANSACTIONS ON ALGORITHMS, 2020, 16 (03)
  • [45] STRUCTURE THEOREM AND ISOMORPHISM TEST FOR GRAPHS WITH EXCLUDED TOPOLOGICAL SUBGRAPHS
    Grohe, Martin
    Marx, Daniel
    SIAM JOURNAL ON COMPUTING, 2015, 44 (01) : 114 - 159
  • [46] The optimized circuit simulation method for isomorphism determination of mixed graphs
    Chen, X., 1600, American Scientific Publishers (07): : 97 - 103
  • [47] A parametric filtering algorithm for the graph isomorphism problem
    Sébastien Sorlin
    Christine Solnon
    Constraints, 2008, 13 : 518 - 537
  • [48] A parametric filtering algorithm for the graph isomorphism problem
    Sorlin, Sebastien
    Solnon, Christine
    CONSTRAINTS, 2008, 13 (04) : 518 - 537
  • [49] A randomized parallel algorithm for planar graph isomorphism
    Gazit, H
    Reif, JH
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1998, 28 (02): : 290 - 314
  • [50] ON THE IMPOSSIBILITY OF A QUANTUM SIEVE ALGORITHM FOR GRAPH ISOMORPHISM
    Moore, Cristopher
    Russell, Alexander
    Sniady, Piotr
    SIAM JOURNAL ON COMPUTING, 2010, 39 (06) : 2377 - 2396
12345