Graph isomorphism and QAP variances.
Valdir Agustinho de Melo, Paulo Oswaldo Boaventura Netto, Peter Hahn, Laura Bahiense · Studia informatica universalis · 2010
Variances of solution values that can be calculated in polynomial time may be associated with an instance of the Quadratic Assignment Problem (QAP). The problem of graph isomorphism can be modeled as a QAP, associating each data matrix with each graph. In this work, we look for invariant edge weight functions for the graphs composing the instances in order to try to find quantitative differences between variances which would be associated with the absence of isomorphism. This technique is sensitive enough to show the effect of a single edge exchange between two regular graphs of up to 2000 vertices and 500,000 edges and between two planar graphs of up to 3000 vertices, within the samples utilized. MOTS-CLES : Isomorphisme de graphes, probleme d’affectation quadratique, variances.