An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants

被引:16
作者
Dehmer, Matthias [1 ]
Grabner, Martin [1 ]
Mowshowitz, Abbe [2 ]
Emmert-Streib, Frank [3 ]
机构
[1] UMIT, Inst Bioinformat & Translat Res, Eduard Wallnoefer Zentrum 1, A-6060 Hall In Tirol, Austria
[2] CUNY City Coll, Dept Comp Sci, New York, NY 10031 USA
[3] Queens Univ Belfast, Computat Biol & Machine Learning Lab, Ctr Canc Res & Cell Biol, Sch Med Dent & Biomed Sci, Belfast BT9 7BL, Antrim, North Ireland
关键词
Graph isomorphism; Graphs; Graph measures; Graph topology; Uniqueness; INFORMATION-THEORY; ALGORITHM; INDEXES; ENTROPY;
D O I
10.1007/s10444-012-9281-0
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The search for an easily computable, finite, complete set of graph invariants remains a challenging research topic. All measures characterizing the topology of a graph that have been developed thus far exhibit some degree of degeneracy, i.e., an inability to distinguish between non-isomorphic graphs. In this paper, we show that certain graph invariants can be useful in substantially reducing the computational complexity of isomorphism testing. Our findings are underpinned by numerical results based on a large scale statistical analysis.
引用
收藏
页码:311 / 325
页数:15
相关论文
共 50 条
  • [1] A graph isomorphism algorithm for object recognition
    Abdulrahim, MA
    Misra, M
    [J]. PATTERN ANALYSIS AND APPLICATIONS, 1998, 1 (03) : 189 - 201
  • [2] Aho A. V., 1974, The design and analysis of computer algorithms
  • [3] [Anonymous], P 9 WORKSH ALG ENG E
  • [4] [Anonymous], 2010, NAUTY
  • [5] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
  • [6] [Anonymous], 1995, J Convex Anal
  • [7] [Anonymous], R SOFTW LANG ENV STA
  • [8] [Anonymous], 2009, ENCY COMPLEXITY SYST, DOI DOI 10.1007/978-0-387-30440-3_285
  • [9] Balaban A., 1999, TOPOLOGICAL INDICES, P21
  • [10] NEW VERTEX INVARIANTS AND TOPOLOGICAL INDEXES OF CHEMICAL GRAPHS BASED ON INFORMATION ON DISTANCES
    BALABAN, AT
    BALABAN, TS
    [J]. JOURNAL OF MATHEMATICAL CHEMISTRY, 1991, 8 (04) : 383 - 397