CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Towards A Promising Edge Classification Algorithm for the Graph Isomorphism Problem

by Islam A. T. F. Taj-eddin, Samir Abou El-seoud, Jihad M. Al-ja’am
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 65 - Number 13
Year of Publication: 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 },
issue_date = { March 2013 },
volume = { 65 },
number = { 13 },
month = { March },
year = { 2013 },
issn = { 0975-8887 },
pages = { 38-43 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume65/number13/10986-6144/ },
doi = { 10.5120/10986-6144 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:18:43.457428+05:30
%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
%J International Journal of Computer Applications
%@ 0975-8887
%V 65
%N 13
%P 38-43
%D 2013
%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
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. Boppana R. , Hastad J. and Zachos S. 1987. Does co-NP have short interactive proofs?, Information Processing Letters 25(2), (1987), pages 127-132.
  7. 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).
  8. Colbourn C. J. 1981. On testing isomorphism of permutation graphs, 1981, Networks 11: 13–21, doi:10. 1002/net. 3230110103.
  9. Cook D. J. and Holder L. B. 2007. Mining Graph Data, John Wiley & Sons, 2007.
  10. Cormen T. H. , Leiserson C. E. , Rivest R. L. and Stein C. 2009. Introduction to algorithms, 3rd edition, the MIT press, 2009.
  11. 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.
  12. Gurevich Y. 1997. From Invariants to Canonization, The Bulletin of European Association for Theory of Computer Science, 1997, Number 63.
  13. Hopcroft J. and Tarjan R. E. 1974. Efficient planarity testing. J. ACM, (1974), 21(4):549–568.
  14. 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.
  15. Irniger C-A M 2005. Graph Matching: Filtering Databases of Graphs Using Machine Learning, Aka, 2005.
  16. Kelly P. J. 1957. A congruence theorem for trees, Pacific J. Math. , 7, 1957, pp. 961–968.
  17. kobler J. , Schoning U. , and Toran J. 1993. The graph isomorphism problem: Its structural complexity. Birkhauser, 1993.
  18. 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/)).
  19. Toran J. 2000. On the hardness of graph isomorphism. FOCS, 2000, 180–186.
  20. 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.
  21. Weisfeiler Boris ed. 1976. On Construction and Identification of Graphs, Lecture Notes in Mathematics 558, Springer, (1976).
  22. 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

Computer Science
Information Sciences

Keywords

Edge Classification Graph Isomorphism Polynomial Algorithm Graph Canonization

Powered by PhDFocusTM