An Optimized Circuit Simulation Method for the Identification of Isomorphic Disconnected Graphs
- PDF / 319,738 Bytes
- 5 Pages / 439.37 x 666.142 pts Page_size
- 31 Downloads / 166 Views
An Optimized Circuit Simulation Method for the Identification of Isomorphic Disconnected Graphs Huiliang Shang · Yuan Gao · Jiajun Zhu
Received: 8 August 2012 / Revised: 25 March 2013 © Springer Science+Business Media New York 2013
Abstract Many algorithms exist to deal with the problem of graph isomorphism, but most of the contemporary algorithms like VF2 have a bad performance for identifying isomorphism of disconnected graphs. In this paper, we propose a method that can filter and remove single vertices so as to eliminate the dependence of the relationship between all vertices which causes the loss of effectiveness. Tests on disconnected graphs demonstrate that this method can solve the problem of identifying isomorphic disconnected graphs in polynomial time. Keywords Disconnected graphs · Graph isomorphism · Associated circuit · Circuit simulation
1 Introduction Graph isomorphism has been widely applied in various fields, including circuit analysis [1, 5], computer vision [2, 3], chemistry [6], and mechanics [8]. We have proposed a new isomorphism identification algorithm called the circuit simulation method in [7, 9, 10]. It can identify the isomorphism of random graphs in polynomial time at the level of O(n2 ). Especially for self-loops, we solved the problem by using the splitting method in [7]. However, almost all the algorithms proposed thus far like VF2 have failed to achieve good performances on disconnected graphs or disconnected non-planar graphs [4] since they only focus on connected graphs. Therefore, H. Shang () · Y. Gao · J. Zhu Department of Electrical Engineering, Fudan University, Shanghai, China e-mail: [email protected] Y. Gao e-mail: [email protected] J. Zhu e-mail: [email protected]
Circuits Syst Signal Process
Fig. 1 Process of optimized circuit simulation method
it is necessary for us to study how to identify isomorphic disconnected graphs and propose a new algorithm to make this process accurate and efficient. If a vertex u cannot connect to another vertex v through a set of edges, the graph is disconnected. Since search algorithms use relationship between vertices to identify the isomorphism of graphs, these algorithms cannot identify disconnected graphs well. Therefore, we have proposed an optimized circuit simulation method with single vertices filtered and removed before the circuit calculation to avoid any failure that may occur. The method uses a change of order of admittance matrix to distinguish single vertices and make the node admittance matrix smaller before the iteration process, and it is able to identify isomorphism of disconnected graphs in polynomial time.
2 Application and Optimization of Circuit Simulation Method Our method is based on our previous circuit simulation method [7, 9, 10]. Since the initial step of the circuit simulation method is to connect every node to the reference, the method is theoretically useful for identifying isomorphic disconnected graphs. But our experiments found that single vertices disturbed the identification progre
Data Loading...
