Journal
MECHANISM AND MACHINE THEORY
Volume 44, Issue 1, Pages 122-139Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.mechmachtheory.2008.02.008
Keywords
The perimeter graph; Kinematic chains; Isomorphism identification; Characteristic adjacency matrix
Categories
Funding
- NSFC [50575197]
- China Postdoctoral Science Foundation [20080430122]
Ask authors/readers for more resources
Isomorphism identification of graphs is one of the most important and challenging problems in the fields of mathematics, computer science and mechanisms, etc. This paper attempts to solve the problem by finding a unique representation of graphs. First, the perimeter loop of a graph is identified from all the loops of the graph obtained through a new algorithm. From the perimeter loop a corresponding perimeter graph is derived, which renders the forms of the graph canonical. Then by relabelling the perimeter graph the canonical perimeter graph is obtained, reducing the adjacency matrices of a graph from hundreds of thousands to several or even just one. On the basis of canonical adjacency matrix set, the unique representation of the graph, the characteristic adjacency matrix, is obtained. In such a way, isomorphism identification, sketching, and establishment of the database of common graphs, including the graphs of kinematic chains, all become easy to realize. Computational complexity analysis shows that, in the field of kinematic chains the approach is much more efficient than McKay's algorithm which is considered the fastest so far. It remains efficient even when the links of kinematic chains increase into the thirties. (C) 2008 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available