A POLYNOMIAL TRANSFORM FOR MATCHING PAIRS OF WEIGHTED GRAPHS

Fundamental symmetric polynomials are used for matching pairs of directed and undirected weighted graphs. A symmetric polynomial is a transform that maps a set of input data (roots of the polynomial) into a set of coefficients that are invariant under permutation of the data set. By using this transformation the weights of two nodes can be compared point-to-point through their corresponding invariant coefficients. The optimum match is obtained when the weights of two nodes are a permutation of each other. Simulation experiments show that close solutions to the correct match can be obtained with this method for both directed and undirected graphs. It is shown that the complexity of the present algorithm is of O(n3).