Fetching the paper…
Reading the bibliography…
We report the current state of the graph isomorphism problem from the practical point of view.
Parris, R. and Read, R. C. 1969. A coding procedure for graphs. Scientific Report. UWI/CC 10. Univ. of West Indies Computer Centre
1969
Earlier work this paper cites.
Corneil, D. G. and Gotlieb, C. C. 1970. An efficient algorithm for graph isomorphism. JACM 17, 51–64
1970
Earlier work this paper cites.
Aho, A. V., Hopcroft, J. E. and Ullman, J. D. 1974. The design and analysis of computer algorithms. Addison-Wesley. p. 86
1974
Earlier work this paper cites.
Arlazarov, V. L., Zuev, I. I., Uskov, A. V. and Faradzev, I. A. 1974. An algorithm for the reduction of finite non-oriented graphs to canonical form. Zh. vȳchisl. Mat. mat. Fiz. 14, 737–743
1974
Earlier work this paper cites.
Beyer, T. and Proskurowski, A. 1975. Symmetries in the graph coding problem. In: Proceedings of NW76 ACM/CIPC Pac. Symp., 198–203
1975
Earlier work this paper cites.
Read, R. C. and Corneil, D. G. 1977. The graph isomorphism disease. J. Graph Theory 1, 339–363
1977
Earlier work this paper cites.
Colbourn, C. S. 1978. A Bibliography of the Graph Isomorphism Problem. Technical Report, University of Toronto
1978
Earlier work this paper cites.
Filotti, I. S. and Mayer, J. N. 1980. A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. In: Proceedings of the 12th ACM Symposium on Theory of Computing, 236–243
1980
Earlier work this paper cites.
McKay, B. D. 1980. Practical graph isomorphism. Congr. Numer. 30, 45–87
1980
Earlier work this paper cites.
Miller, G. L. 1980 Isomorphism testing for graphs of bounded genus. In: Proceedings of the 12th ACM Symposium on Theory of Computing, 225–235
1980
Earlier work this paper cites.
Colbourn, C. S. and Booth, K. S. 1981. Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM J. Comput. 10, 203–225
1981
Earlier work this paper cites.
Luks, E. 1982. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comp. System Sci. 25, 42–65
1982
Cited alongside, same era.
Babai, L., Kantor, W. M. and Luks, E. M. 1983. Computational complexity and the classification of finite simple groups. In: Proceedings of the 24th Annual Symposium on the Foundations of Computer Science, 162–171
1983
Cited alongside, same era.
Butler, G. and Lam, C. W. H. 1985 A general backtrack algorithm for the isomorphism problem of combinatorial objects. J. Symbolic Computation 1, 363–381
1985
Cited alongside, same era.
Kirk, A. 1985. Efficiency considerations in the canonical labelling of graphs. Technical report TR-CS-85-05, Computer Science Department, Australian National University
1985
Cited alongside, same era.
Darga, P. T., Liffiton, M. H., Sakallah, K. A. and Markov, I. L. 2004. Exploiting structure in symmetry detection for CNF. In: Proceedings of the 41st Design Automation Conference, 530–534
2004
Later among the works it cites.
Darga, P. T., Sakallah, K. A. and Markov, I. L. 2004. Faster Symmetry Discovery using Sparsity of Symmetries. In: Proceedings of the 45th Design Automation Conference, 149–154
2004
Later among the works it cites.
Junttila, T. and Kaski, P. 2007. Engineering an efficient canonical labeling tool for large and sparse graphs. In: Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics, 135–149
2007
Later among the works it cites.
López-Presa, J. L. and Fernández Anta, A. 2009. Fast algorithm for graph isomorphism testing. In: Proceedings of the 8th International Symposium on Experimental Algorithms, 221–232
2009
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
1988
Cited alongside, same era.
Bodlaender, H. 1990. Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J. Algorithms 11, 631–643
1990
Cited alongside, same era.
Leon, J. S. 1990. Permutation group algorithms based on partitions, I: Theory and algorithms. J. Symbolic Comput. 43, 545–581
1990
Cited alongside, same era.
Goldreich, O., Micali, S. and Wigderson, A. 1991. Proofs that yield nothing but their validity, or all languages in np have zero-knowledge proof systems. JACM 38, 690–728
1991
Cited alongside, same era.
Kocay, W. 1996. On writing isomorphism programs. In: Wallis, W. D. (Ed.), Computational and Constructive Design Theory, Kluwer, 135–175
1996
Cited alongside, same era.
Foggia, P., Sansone, C. and Vento, M. 2001. A performance comparison of five algorithms for graph isomorphism. In: Proceedings of the 3rd IAPR TC-15 Workshop on Graph-based Representations in Pattern Recognition, 188–199
2001
Cited alongside, same era.
Seress, Á. 2003. Permutation Group Algorithms. Cambridge University Press, pp. x+264
2003
Cited alongside, same era.
McKay, B. D 1978a. Backtrack programming and isomorph rejection on ordered subsets. Ars Combin. 5, 65–99
Cited in the paper.
Grohe, M. 2010. Fixed-point definability and polynomial time on graphs with excluded minors. In: Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, 179–188
2010
Later among the works it cites.
2010
Later among the works it cites.
Junttila, T. and Kaski, P. 2011. Conflict Propagation and Component Recursion for Canonical Labeling. In: Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms, 151–162
2011
Later among the works it cites.
2011
Later among the works it cites.
2011
Later among the works it cites.
Grohe, M. 2012. Structural and Logical Approaches to the Graph Isomorphism Problem, In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 188
2012
Later among the works it cites.