UM
A fast algorithm for kinematic chain isomorphism identification based on dividing and matching vertices
Zeng K.; Fan X.; Dong M.; Yang P.
2014
Source PublicationMechanism and Machine Theory
ISSN0094114X
Volume72Pages:25
AbstractKinematic chain isomorphism identification is a crucial issue in mechanism topology and an important application of Graph Isomorphism to mechanisms. In this paper, a kinematic chain is uniquely represented by a graph, and a fast deterministic algorithm called the Dividing and Matching Algorithm (DMA) is proposed. First, the vertices of each graph are divided by the degree. Then, vertex connection properties in a sub-graph and between sub-graphs are explored. Accordingly the expanded square degree and the correlation degree are proposed, based on which, the Dividing Vertex Algorithm (DVA) is developed to divide vertices into sets. Moreover, it is proved that only the vertices from the corresponding sets between two graphs are possible to be bijective or matched, which avoids exhaustive search. Eventually, a backtracking procedure is employed to match the vertices between corresponding sets by calling up DVA repeatedly. DMA detects whether the adjacency matrices of two graphs can be adjusted to be equivalent by changing the orders of vertices. Justifications for the reliability of each part of DMA are provided. The experiments and comparisons with existing algorithms show the effectiveness and efficiency of DMA. © 2013 Elsevier Ltd. All rights reserved.
KeywordBacktracking Isomorphism identification Kinematic chain Vertex division Vertex match
DOI10.1016/j.mechmachtheory.2013.09.011
URLView the original
Language英语
The Source to ArticleScopus
Fulltext Access
Citation statistics
Cited Times [WOS]:12   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionUniversity of Macau
Recommended Citation
GB/T 7714
Zeng K.,Fan X.,Dong M.,et al. A fast algorithm for kinematic chain isomorphism identification based on dividing and matching vertices[J]. Mechanism and Machine Theory,2014,72:25.
APA Zeng K.,Fan X.,Dong M.,&Yang P..(2014).A fast algorithm for kinematic chain isomorphism identification based on dividing and matching vertices.Mechanism and Machine Theory,72,25.
MLA Zeng K.,et al."A fast algorithm for kinematic chain isomorphism identification based on dividing and matching vertices".Mechanism and Machine Theory 72(2014):25.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zeng K.]'s Articles
[Fan X.]'s Articles
[Dong M.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zeng K.]'s Articles
[Fan X.]'s Articles
[Dong M.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zeng K.]'s Articles
[Fan X.]'s Articles
[Dong M.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.