A General Vertex Partition Refinement Algorithm for Graph Isomorphism

Ai Min Hou; Chuan Fu Hu; Zhi Feng Hao

doi:10.4028/www.scientific.net/AMR.760-762.1919

Paper Titles

Analysis of Web Log Data Mining Based on Improved Fuzzy Clustering Algorithm
p.1896

A Method on Process Planning Decision Based on Genetic Algorithm
p.1902

A Hybird Virtual Machine Placement Aglrithm for Virtualized Desktop Infrastructure
p.1906

Curve-Skeleton Extraction Using Appropriate Threshold Optimization
p.1911

A General Vertex Partition Refinement Algorithm for Graph Isomorphism
p.1919

Research of Clustering Algorithm Based on Different Data Field Model
p.1925

Structure Design of the Database in the INS/Database Matching Navigation System
p.1930

Construction Security Architecture of the Internet of Things Based on IPv6 Technology
p.1936

Automatic Translation in Chinese and English Based on Mixed Strategy
p.1942

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 760-762A General Vertex Partition Refinement Algorithm...

A General Vertex Partition Refinement Algorithm for Graph Isomorphism

Abstract:

A general depth-first backtracking algorithm for graph isomorphism with the vertex partition and refinement technique is presented in this paper. The time complexity of this nondeterministic polynomial algorithm is O(nα+3) where nα is the number of backtracking points and (h-1)/2α (h+1)/2 for h=logn in the worst cases. The tests on many types of graphs validated the efficiency of this algorithm for graph isomorphism.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 760-762)

Pages:

1919-1924

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.760-762.1919

Citation:

Cite this paper

Online since:

September 2013

Authors:

Ai Min Hou, Chuan Fu Hu, Zhi Feng Hao

Keywords:

Algorithm (GA), Component, Invariant, Partition, Refinement

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] J.R. Ullmann, An algorithm for subgraph isomorphism, J. of the Association for Computer Machinery, vol. 23(1), p.31–42, (1976).

Google Scholar

[2] L.P. Cordella, P. Foggia, C. Sansone, Subgraph transformations for the inexact matching of attributed relational graphs, Computing Supplement, vol. 12, p.43–52, (1998).

DOI: 10.1007/978-3-7091-6487-7_5

Google Scholar

[3] L.P. Cordella, P. Foggia, C. Sansone, An improved algorithm for matching large graphs, International Workshop on Graph-based Representation in Pattern Recognition, Ischia, Italy, p.149–159, (2001).

Google Scholar

[4] B.D. McKay, Practical graph isomorphism, Congressus Numberantium, vol. 30, pp.45-87, (1981).

Google Scholar

[5] T. Miyazaki, The complexity of Mckay's canonical labeling algorithm, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 28, pp.239-256, (1997).

DOI: 10.1090/dimacs/028/14

Google Scholar

[6] X.X. Zou, Q. Dai, A Vertex Refinement Method for Graph Isomorphism, J. of Software, Vol. 18(2), pp.213-219, (2007).

Google Scholar

[7] D.C. Schmidt, L.E. Druffel, A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices, J. of the Association for Computer Machinery, vol. 23(3), pp.433-445, (1976).

DOI: 10.1145/321958.321963

Google Scholar

[8] M. Oliveria, F. Greve, A new refinement procedure for graph isomorphism algorithms, Proc. of the GRACO, pp.373-379, (2005).

Google Scholar

[9] A.M. Hou, Z.F. Hao, A Polynomial Time Algorithm for Undirected Graph Isomorphism, Proc. of the World Congress on Engineering, pp.1236-1239, (2011).

Google Scholar

[10] A.M. Hou, Elementary operations on a matrix to determine the isomorphism of graphs, J. of Computer Engineering and Applications, vol. 42(20), pp.51-54, (2006).

Google Scholar

[11] The Graph Data, Collection of isomorphic graphs, http: /amalfi. dis. unina. it/graph.

Google Scholar

[12] A.J.L. Paulus, Conference matrices and graphs of order 26, Technische Hogeschool Eindhoven, report WSK 73/06, Eindhoven, pp.89-93, (1973).

Google Scholar