Determination of isomorphism and its applications for arbitrary graphs based on circuit simulation

被引：7

作者：

Li, Feng

Shang, Huiliang ^{[2
]}

Woo, Peng-Yung ^{[1
]}

机构：

[1] No Illinois Univ, Dept Elect Engn, De Kalb, IL 60115 USA

[2] Fudan Univ, Dept Elect Engn, Shanghai 200433, Peoples R China

来源：

CIRCUITS SYSTEMS AND SIGNAL PROCESSING | 2008年 / 27卷 / 05期

基金：

英国科研创新办公室;

关键词：

arbitrary graphs; graph isomorphism; adjoint circuit; computational complexity;

D O I：

10.1007/s00034-008-9054-7

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

The adjoint circuit of an arbitrary graph is established and is then solved by using circuit analysis methods. The solved node voltages are used to determine the correspondence of the vertices in the original graphs. A new method for the determination of an isomorphism for arbitrary graphs is therefore proposed.

引用

页码：749 / 761

页数：13

共 13 条

[1] Agusa K., 1992, RNNS/IEEE Symposium on Neuroinformatics and Neurocomputers (Cat. NO.92TH0483-8), P1142, DOI 10.1109/RNNS.1992.268621
[2] CHEN SB, 1982, NETWORK GRAPH THEORY, P176
[3] 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
[4] GAREY MR, 1979, COMPTUERS INTRACTABI
[5] Exact and approximate graph matching using random walks
Gori, M
Maggini, M
Sarti, L
[J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2005, 27 (07) : 1100 - 1111
[6] Li F, 1999, INT J IMAG SYST TECH, V10, P355, DOI 10.1002/(SICI)1098-1098(1999)10:4<355::AID-IMA7>3.0.CO
[7] 2-7
[8] LIN C, 1996, IEEE T PARALL DISTR, V7, P306
[9] ISOMORPHISM OF GRAPHS OF BOUNDED VALENCE CAN BE TESTED IN POLYNOMIAL-TIME
LUKS, EM
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1982, 25 (01) : 42 - 65
[10] MALIK SHK, 2003, P IEEE INMIC, P396

← 1 2 →