Research Article
Towards A Promising Edge Classification Algorithm for the Graph Isomorphism Problem
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 65 - Issue 13 |
| Published: March 2013 |
| Authors: Islam A. T. F. Taj-Eddin, Samir Abou El-Seoud, Jihad M. Al-Ja’Am |
10.5120/10986-6144
|
Islam A. T. F. Taj-Eddin, Samir Abou El-Seoud, Jihad M. Al-Ja’Am . Towards A Promising Edge Classification Algorithm for the Graph Isomorphism Problem. International Journal of Computer Applications. 65, 13 (March 2013), 38-43. DOI=10.5120/10986-6144
@article{ 10.5120/10986-6144,
author = { Islam A. T. F. Taj-Eddin,Samir Abou El-Seoud,Jihad M. Al-Ja’Am },
title = { Towards A Promising Edge Classification Algorithm for the Graph Isomorphism Problem },
journal = { International Journal of Computer Applications },
year = { 2013 },
volume = { 65 },
number = { 13 },
pages = { 38-43 },
doi = { 10.5120/10986-6144 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2013
%A Islam A. T. F. Taj-Eddin
%A Samir Abou El-Seoud
%A Jihad M. Al-Ja’Am
%T Towards A Promising Edge Classification Algorithm for the Graph Isomorphism Problem%T
%J International Journal of Computer Applications
%V 65
%N 13
%P 38-43
%R 10.5120/10986-6144
%I Foundation of Computer Science (FCS), NY, USA
Abstract
For over three decades the Graph Isomorphism (GI) problem has been extensively studied by many researchers in algorithms and complexity theory. To date, there is no formal proof to classify this problem to be in the class P or the class NP. In this paper, evidence had been proposed of the existing of polynomial time algorithm based on edge classification which can be used to prove that GI is rather in the class P.
References
- Arvind V. , and Toran J. 2005. Isomorphism Testing: Perspective and Open Problems, Bulletin of the European Association for Theoretical Computer Science, Computational Complexity Column, (June, 2005), Number 86.
- Babai L. 1996. Automorphism groups, isomorphism, reconstruction, Handbook of Combinatorics (eds. R. L. Graham, M. Grotschel and L. Lovasz), Chapter 27, North-Holland, Amsterdam, (1996), pages 1447-1540.
- Babai L. and Kucera L. 1979. Canonical labeling of graphs in average linear time. Proc. 20th Annual IEEE Symposium on Foundations of Computer Science, 1979, 39–46.
- Babai L. and Luks M. 1983. Canonical labeling of graphs. In proceedings of the fifteenth annual ACM symposium on theory of computing, 1983, page 171-183.
- Baird H. S. , Cho Y. E. 1975. An artwork design verification system, Proceedings of the 12th Design Automation Conference. IEEE Press. , (1975) , pp. 414-420.
- Boppana R. , Hastad J. and Zachos S. 1987. Does co-NP have short interactive proofs?, Information Processing Letters 25(2), (1987), pages 127-132.
- Cai J. , Furer M. , and Immerman N. 1992. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389-410, (1992).
- Colbourn C. J. 1981. On testing isomorphism of permutation graphs, 1981, Networks 11: 13–21, doi:10. 1002/net. 3230110103.
- Cook D. J. and Holder L. B. 2007. Mining Graph Data, John Wiley & Sons, 2007.
- Cormen T. H. , Leiserson C. E. , Rivest R. L. and Stein C. 2009. Introduction to algorithms, 3rd edition, the MIT press, 2009.
- Gary M. R. and Johnson D. S. 2000. Computers and Intractability a Guide to the Theory of NP-Completeness, W. H. FREEMAN AND COMPANY, NY, 1979, pp. 155-156.
- Gurevich Y. 1997. From Invariants to Canonization, The Bulletin of European Association for Theory of Computer Science, 1997, Number 63.
- Hopcroft J. and Tarjan R. E. 1974. Efficient planarity testing. J. ACM, (1974), 21(4):549–568.
- Hopcroft J. and Wong J. 1974. Linear time algorithm for isomorphism of planar graphs, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, 1974, pp. 172–184, doi:10. 1145/800119. 803896.
- Irniger C-A M 2005. Graph Matching: Filtering Databases of Graphs Using Machine Learning, Aka, 2005.
- Kelly P. J. 1957. A congruence theorem for trees, Pacific J. Math. , 7, 1957, pp. 961–968.
- kobler J. , Schoning U. , and Toran J. 1993. The graph isomorphism problem: Its structural complexity. Birkhauser, 1993.
- McKAY B. D. 1981. Practical Graph Isomorphism. Congr. Numerantium ,(1981), 30, 45-87. (Nauty User's Guide, Version 2. 2 (beta 6); (2003) (http://cs. anu. edu. au/people/bdm/nauty/)).
- Toran J. 2000. On the hardness of graph isomorphism. FOCS, 2000, 180–186.
- Toran J. and Wagner F. 2009. The complexity of planar graph isomorphism, Bulletin of the European Association for Theoretical Computer Science, Computational Complexity Column, (February 2009), Number 97.
- Weisfeiler Boris ed. 1976. On Construction and Identification of Graphs, Lecture Notes in Mathematics 558, Springer, (1976).
- Weisfeiler B. and A. A. Lehman 1968. A Reduction of a Graph to a Canonical Form and an Algebra Arising during this Reduction, (in Russian), Nauchno-Technicheskaya Informatsia, Seriya 2, 9 (1968), 12-16.
Index Terms
Keywords