中文

Journal of Applied Sciences >

2014 , Vol. 32 >Issue 2: 199 - 208

DOI: https://doi.org/10.3969/j.issn.0255-8297.2014.02.013

Electronic Engineering

Application of Optimized Circuit Simulation—Identification of Isomorphic Hybrid Switching

Expand
  • 1. Department of Electronic Engineering, Fudan University, Shanghai 200433, China
    2. East Electron Limited Company, Yantai 264000, Shandong Province, China

Received date: 2011-11-17

  Revised date: 2012-10-14

  Online published: 2012-10-14

Fold

Abstract

This paper presents a new method for graph isomorphism identification and applies it to the identification of isomorphic hybrid switching topology. A mathematical model of hybrid switching topology is first introduced. The adjacency matrix and undirected-weighted graph description of the hybrid switching
topology are presented according to the mathematical model. In this case, the problem of identifying isomorphic hybrid switching topology is transformed into isomorphism determination of the corresponding undirectedweighted graphs. An optimized version of the circuit simulation method previously presented by the authors is proposed to solve the graph isomorphism determination problem. With a small modification, the optimized circuit simulation method can solve the problem of graph isomorphism determination more efficiently. Tests of the proposed method and another method called the eigenvalue algorithm are applied in the identification of isomorphic hybrid switching topology. The results show that the optimized circuit simulation method is valid and has advantages in both identification efficiency and ability of matching corresponding vertices of the isomorphic hybrid switching topology.

Key words：  switching topology; isomorphism; circuit simulation method; eigenvalue algorithm

Cite this article

SHANG Hui-liang1, LIU Yang1, LIU Zhi-dong1, DONG Wen-jie2, LI Feng1 . Application of Optimized Circuit Simulation—Identification of Isomorphic Hybrid Switching[J]. Journal of Applied Sciences, 2014 , 32(2) : 199 -208 . DOI: 10.3969/j.issn.0255-8297.2014.02.013

References

[1] 石勇，杨旭，何群，王兆安. 同构混合开关拓扑的辨识[J]. 中国电机工程学报，2003, 23(11): 116-121.

SHI Y, YANG X, HE Q, WANG Z. Identification of hybrid switching topology[J]. Proceedings of the Chinese society for electrical engineering, 2003, 23(11): 116-121. (in Chinese)

[2] 丁华锋，黄真. 平面机构统一拓扑描述模型的建立及同构判别[J]. 机械工程学报，2009, 45(3): 99-103.

DING H, HUANG Z. Uniform topological representation model of planar mechanisms and isomorphism identification[J]. Journal of Mechanical Engineering, 2009, 45(3): 99-103.

(in Chinese)

[3] 丁玲，路懿. 运动链拓扑图的特征数组表示及同构判断[J]. 机械工程学报，2010, 46(7): 63-67.

DING L, LU Y. Character arrays representation and isomorphism identification of kinematic chain topology graphs[J]. Journal of Mechanical Engineering, 2010, 46(7): 63-67. (in Chinese)

[4] GOLOVIN A, HENRICK K. Chemical Substructure Search in SQL[J]. Journal of chemical information and modeling, 2009, 49(1): 22-27.

[5] CHEN K, GUO C, WU H, YUAN J, FENG Z, CHEN Y, LU S, WU W. Generic and automatic address configuration for data center networks [C]// Proceedings of the ACM SIGCOMM 2010 Conference. New Delhi, India, 2010: 39-50.

[6] SHANG H, LI F, TANG X, WOO P Y. A New Algorithm for isomorphism determination of undirected graphs-circuit simulation method[J]. Circuits, Systems, and Signal Processing, 2011, 30(5): 1115-1130.

[7] LI F, SHANG H, WOO P Y. Determination of isomorphism and its applications for arbitrary graphs based on circuit simulation[J]. Circuits, Systems, and Signal Processing, 2008, 27(5): 749-761.

[8] SHANG H, LI J, CAI Q, DONG W. An optimized algorithm for the identification of isomorphic undirected graphs [C]// Proceedings of 2011 International Conference on Modelling, Identification and Control, ICMIC 2011, Shanghai, 2011: 351-356.

[9] 李锋，李晓艳. 图的同构判定算法：关联度序列法及其应用[J]. 复旦学报：自然科学版，2001, 40(3):  318-325.

LI F, LI X. Isomorphism testing algorithm for graphs: incidence degree sequence method and applications [J]. Journal of Fudan University: Science Edition, 2001, 40(3)：318-325. (in Chinese)

[10] 李锋，商慧亮. 有向图的同构判定算法:出入度序列法[J]. 应用科学学报，2002, 20(3): 258-262.

LI F, SHANG H. An isomorphism testing algorithm for directed graphs: the in-degree and out-degree sequence method[J]. Journal of Applied Science, 2002, 20(3): 258-262. (in Chinese)

[11] 南晋华，齐欢. 图同构问题的决策神经网络模型[J]. 计算机学报，2010, 33(2): 300-304.

NAN J, QI H. The decision-making neural networks model for solving the graph isomorphism problem[J]. Chinese Journal of Computers, 2010, 33(2): 300-304. (in Chinese)

[12] PORUMBEL D C. Isomorphism testing via polynomial-time graph extensions[J]. Journal of Mathematical Modeling and Algorithms, 2010, 10(2): 119-143.

[13] ZAHIDI U A. Spectral solution for detecting isomorphic graphs with nondegenerate eigenvalues[C]// 11th IEEE International Multitopic Conference, INMIC2007. Lahore, Pakistan, 2007: 1-4.

[14] QIU M, HU H, JIANG Q, HU H. A new approach of graph isomorphism detection based on decision tree[C]//2nd International Workshop on Education Technology and Computer Science, ETCS 2010, Wuhan, Hubei, 2010: 32-35.

[15] ZHANG B, TANG Y, WU J, HUANG L. A unique vertex deleting algorithm for graph isomorphism [C]//2011 International Symposium on Image and Data Fusion, 2011, Tengchong, Yunnan, 2011: 1-4.

[16] 徐俊明. 图论及其应用 [M]. 安徽：中国科学技术大学出版社，1998:16.

 [17] A. Meister. Numerik linearer Gleichungssysteme[M].  2nd ed. Germany: View
Options
Outlines

/

〈 〉