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

被引：0
作者：
Matthias Dehmer
Martin Grabner
Abbe Mowshowitz
Frank Emmert-Streib
机构：
[1] UMIT,Institute for Bioinformatics and Translational Research
[2] The City College of New York (CUNY),Department of Computer Science
[3] Queen’s University Belfast,Computational Biology and Machine Learning Lab, Center for Cancer Research and Cell Biology, School of Medicine, Dentistry and Biomedical Sciences
来源：
Advances in Computational Mathematics | 2013年 / 39卷
关键词：
Graph isomorphism; Graphs; Graph measures; Graph topology; Uniqueness; 05C60; 05C75; 68R10;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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
页数：14
相关论文
共 67 条
[1]  
Abdulrahim M(1998)A graph isomorphism algorithm for object recognition Pattern Anal. Appl. 1 189-201
[2]  
Misra M(1991)New vertex invariants and topological indices of chemical graphs based on information on distances J. Math. Chem. 8 383-397
[3]  
Balaban AT(1981)Isomer discrimination by topological information approach J. Comput. Chem. 2 127-148
[4]  
Balaban TS(1977)Information theory, distance matrix and molecular branching J. Chem. Phys. 67 4517-4533
[5]  
Bonchev D(2004)Thirty years of graph matching in pattern regocnition Int. J. Pattern Recogn. 18 265-298
[6]  
Mekenyan O(1970)An efficient algorithm for graph isomorphism J. ACM 17 51-64
[7]  
Trinajstić N(2011)A history of graph entropy measures Inform. Sci. 1 57-78
[8]  
Bonchev D(2010)New polynomial-based molecular descriptors with low degeneracy PLoS ONE 57 e11393-1663
[9]  
Trinajstić N(2009)On entropy-based molecular descriptors: Statistical analysis of real and synthetic chemical structures J. Chem. Inf. Model. 49 1655-39
[10]  
Conte D(2011)Network analysis using a novel highly discriminating topological index Complexity 16 32-876
1234567