Education, Science, Technology, Innovation and Life
Open Access
Sign In
  1. Home
  2. Journals
  3. Advances in Computer, Signals and Systems
  4. Vol 7, Issue 3, 2023

A Study of Isomorphic Trees in Programming Competitions

Download as PDF

DOI: 10.23977/acss.2023.070312 | Downloads: 17 | Views: 419

Author(s)

Zhiyong Feng 1, Yike Shi 1, Junping Shi 1

Affiliation(s)

1 The School of Computer Science and Engineering, Jishou University, Jishou, Hunan, 416000, China

Corresponding Author

Junping Shi

ABSTRACT

Tree isomorphism refers to the question whether two trees are exactly the same when the structure and node labels are the same. Tree isomorphism algorithm can be used to judge whether two trees are similar and classify similar trees. Tree isomorphism algorithms are usually implemented using depth-first search and hash tables, and there are also methods using graph theory and linear algebra algorithms. Tree isomorphism algorithm is widely used in many fields, such as bioinformatics, computer science and mathematics. It can help researchers better understand and analyze tree-structured data and provide a basis for subsequent research and development. At the same time in college students programming competition for the problem of tree isomorphism is more widely studied, usually use Algorithm of Aho, Hopcroft, and Ullman(AHU) to solve the isomorphism tree, but simple AHU algorithm time complexity is, cannot well solve the problem in the competition, consider to improve the AHU algorithm. This paper starts from the definition of homogenous tree, tells the basic concept of homogenous tree, then introduces the principle and implementation of naive AHU algorithm and analyzes its time complexity, and then improves the naive AHU algorithm, which greatly improves the running efficiency of AHU algorithm, and finally introduces the application of improved AHU in the form of program design competition.

KEYWORDS

ACM programming, tree isomorphism determination algorithm, tree isomorphism, algorithm optimization

CITE THIS PAPER

Zhiyong Feng, Yike Shi, Junping Shi. A Study of Isomorphic Trees in Programming Competitions. Advances in Computer, Signals and Systems (2023) Vol. 7: 101-105. DOI: http://dx.doi.org/10.23977/acss.2023.070312.

REFERENCES

[1] Yonghui Wu and Jiande Wang. Algorithm Design Practice for Collegiate Programming Contests and Education. CRC Press, 2018
[2] Ferrada Héctor. A sorting algorithm based on ordered block insertions. Journal of Computational Science, 2022, 64
[3] Rick H. de Boer and Cassio P. de Campos. A retrospective overview of International Collegiate programming contest data. Data in Brief, 2019, 25: 104382.
[4] Dovier A, Formisano A, Gupta G, et al. Parallel Logic Programming: A Sequel[J]. arXiv e-prints, 2021. 
[5] Andre Droschinsky and Nils Kriege and Petra Mutzel. Faster Algorithms for the Maximum Common Subtree Isomorphism Problem. CoRR, 2016, abs/1602.07210
[6] V. Arvind et al. The isomorphism problem for k -trees is complete for logspace. Information and Computation, 2012, 217: 1-11.
[7] Mitchell S, Beyer T, Jones W. Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs. Journal of the Acm, 1979, 26(4):603-610.
[8] Cole R, Crochemore M, Galil Z, et al. Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions[C]// IEEE Foundations of Computer Science. IEEE Computer Society, 1993.
[9] Buss S R. Alogtime Algorithms for Tree Isomorphism, Comparison, and Canonization. 1997.
[10] Wang Y K, Fan K C, Liu C W, et al. [IEEE 1995 IEEE International Conference on Evolutionary Computation - Perth, WA, Australia (29 Nov.-1 Dec. 1995)] Proceedings of 1995 IEEE International Conference on Evolutionary Computation - Adaptive optimization for solving a class of subgraph isomorp[J].  1995, 1:44. 
[11] Hopfield J. Neural computation of decisions in optimization problems. Biological Cybernetics, 1985, 52.
[12] Guo Zhengchu and Hu Ting and Shi Lei. Distributed spectral pairwise ranking algorithms. Inverse Problems, 2023, 39(2).

Subscription
E-Mail Alert
Most popular papers
Call for Special Issue
Publication Ethics & OA Statement
Plagiarism Policy
Contact Us
Downloads: 13213
Visits: 256497

Sponsors, Associates, and Links

All published work is licensed under a Creative Commons Attribution 4.0 International License.

Copyright © 2016 - 2031 Clausius Scientific Press Inc. All Rights Reserved.