GENERAL-METHOD FOR THE COMPUTATION OF MATCHING POLYNOMIALS OF GRAPHS

A novel algorithm based on search is developed for computation of matching polynomials of graphs, viewing the edges as ordered pairs. The acyclic Sach's subgraphs of matching polynomials are generated by disjoint-set-union operation. The algorithm is recursive and very general and hence is more compact and has a wide range of applications. The present approach uses artificial intelligence techinques tactfully for partially offsetting combinatorial explosion. This algorithm is more advantageous in terms of space complexity, and its time complexity is exponential as would normally be the case due to nondeterministic polynomial (NP) complete nature of the problem.