A Novel Algorithm Based on the Degree Tree for Graph Isomorphism

被引：0

作者：

Hao, Long ^{[1
]}

机构：

[1] Jiangxi Normal Univ, Sch Software, Nanchang 330022, Peoples R China

来源：

ADVANCED RESEARCH ON AUTOMATION, COMMUNICATION, ARCHITECTONICS AND MATERIALS, PTS 1 AND 2 | 2011年 / 225-226卷 / 1-2期

关键词：

graph isomorphism; degree tree; graph matching; pruning technology;

D O I：

10.4028/www.scientific.net/AMR.225-226.417

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The graph isomorphism problem is to study the relationship between two graphs which seem to be different, but essentially identically. A novel algorithm based on the degree tree is proposed, where each node of the tree describes a given vertex and its neighboring information of a graph. Two vertexes in different graphs are regarded as mapping if the corresponding nodes and all their junior nodes are similar. Hence by comparing their degree trees, two graphs can be determined whether matching or not, and the mapping vertexes can be found. Experimental results show the approach's performance.

引用

页码：417 / 421

页数：5

共 12 条

[1] CHEN L, 2002, COMPUTER ENG, V28
[2] Thirty years of graph matching in pattern recognition
Conte, D
Foggia, P
Sansone, C
Vento, M
[J]. INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2004, 18 (03) : 265 - 298
[3] Cordella L. P., 2001, P 3 IAPR TC 15 INT W
[4] A (sub)graph isomorphism algorithm for matching large graphs
Cordella, LP
Foggia, P
Sansone, C
Vento, M
[J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2004, 26 (10) : 1367 - 1372
[5] Cordella LP, 1998, COMP SUPPL, V12, P43
[6] CORDELLA LP, 2000, P 15 INT C PATT REC, V2, P1038
[7] FOGGIA P, 2001, P 3 IAPR TC 15 WORKS
[8] Li Feng, 2001, Journal of Fudan University (Natural Science), V40, P318
[9] MASSARO A, 2001, P 3 IAPR TC15 WORKSH, P160
[10] McKay B., 1981, Congr. Numer., V30, P45

← 1 2 →