Combinatorics and Graph Theory

1204 Submissions

[1] viXra:1204.0019 [pdf] submitted on 2012-04-05 03:07:16

On Pseudo trees and Graph Isomorphism

Authors: Dhananjay P. Mehendale
Comments: 7 pages.

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.
Category: Combinatorics and Graph Theory