Istituto di Scienza e Tecnologie dell'Informazione     
Levi G. Graph isomorphism: a heuristic edge-partitioning-oriented algorithm. Internal note IEI-B72-16, 1972.
An algorithm for testing isomorphism of two directed or undirected graphs G1 and G2 is described. As in most known graph isomorphism procedures, nodes are partitioned into node cells. Nodes ni1 and nj2,of G1 and G2 respectively, are assigned to different node cells, if node ni1 cannot be mapped onto nj2 by an isomorphism of G1 onto G2 , i.e. if ni1 and nj2 are “different” with respect to a property (feature) which is invariant under isomorphism. The present algorithm considers edge cells also. Edges are partitioned into cells by applying edge features. Several node and edge features of different complexity are available and are used whenever simpler features fail to cause a partitioning. Extended features, defined in terms of node and edge cells, can also be used. Two very simple features ( basic features), exploiting relationships between node and edge cells, are then used iteratively with the aim of refining initial partitions (Algorithm1 ). When such features do not cause any further refinement, a steady situation is reached, in which node and edge cells are compatible. Compatible node and edge cells can be represented by means of their connectivity graph C. Several properties of graph C are derived and a sufficient condition for isomorphism to be tested on C is proven. A partially enumerative technique (Algorithm 2) is described which allows to derive all the isomorphisms. A pair of nodes is selected, i.e. is considered a pair of corresponding nodes, and Algorithm 1 is applied to possibly refine actual partitions, leading to an updated graph C. The process of node selection which is guided by an heuristic estimate of the “best" pair of nodes, is interrupted when the sufficient condition for isomorphism is verified. The non-enumerative steps of the procedure require a number of steps which depends, in the worst case, upon n5, if n is the order of G1 and G2. The application of the procedure to several graphs has shown that, for most graphs, the computation time of Algorithm 2, which is inherently enumerative, depends upon n6.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional