QAPV: a polynomial invariant for graph isomorphism testing

Pesquisa Operacional

Valdir Agustinho De Melo²  Paulo Oswaldo Boaventura-netto¹  Laura Bahiense¹ 

[1] ,Universidade Federal do Rio de Janeiro COPPE Program of Production Engineering,Brazil

关键词: graph isomorphism;    quadratic assignment problem;    variance;   

DOI  :  10.1590/S0101-74382013000200002

来源: SciELO

【 摘 要 】

To each instance of the Quadratic Assignment Problem (QAP) a relaxed instance can be associated. Both variances of their solution values can be calculated in polynomial time. The graph isomorphism problem (GIP) can be modeled as a QAP, associating its pair of data matrices with a pair of graphs of the same order and size. We look for invariant edge weight functions for the graphs composing the instances in order to try to find quantitative differences between variances that could 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 3,000 vertices and 300,000 edges with degrees up to 200. Planar graph pairs from a dense family up to 300,000 vertices were also discriminated. We conjecture the existence of functions able to discriminate non-isomorphic pairs for every instance of the problem.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License