An LP-based procedure for graph isomorphism

Abstract

Graph theory deals with the connection aspects of system of network. No efficient polynomial-bound algorithm for graph isomorphism problem is available. An LP-based algorithm is developed and tested in this thesis. The techniques used in algorithm formulation are based on algebraic transformations which use the Hermite normal form computation, and a direct integer reduction. These transformations lead to a simplified linear system the computation of whom is bounded by a polynomial of O(2n⁴ Log²n). An LP-based algorithm is then used to solve the reduced system. The developed algorithm is coded in Fortran and tested on IBM 3090-150E and AMDAHL 5850. The reduced linear problem is solved as a linear program on 80386 machine using Hyperlindo (version 5.1, 1993) for linear programming. Most of the simulation tests with Hyperlindo provide integer solutions. An exponential time algorithm 'Brute Search' is also coded in Fortran to compare with the developed one. Conclusion and further research direction in this algorithm are provided.