Authors: Dhananjay P. Mehendale
In this paper we obtain a new polynomial time algorithm for testing isomorphism of graphs. This algorithm is based on the idea of associating a rooted, unordered, pseudo tree with given graphs and thus reducing the isomorphism problem for graphs to isomorphism problems for associated rooted, unordered, pseudo trees. We show that isomorphism of the rooted, unordered, pseudo trees associated with graphs and so in effect isomorphism of given two graphs can be tested in polynomial (quadratic) time.
Comments: 7 pages.
[v1] 2012-04-05 03:07:16
Unique-IP document downloads: 144 times
Add your own feedback and questions here: