International Journal of Nonlinear Analysis and Applications

A method for analyzing the problem of determining the maximum common fragments of temporal directed tree, that do not change with time

Document Type : Research Paper

Author

Department of Applied Mathematics, College of Science University of Anbar, Ramadi, Iraq

Abstract

In this study two actual types of problems are considered and solved: 1) determining the maximum common connected fragment of the T-tree (T-directed tree) which does not change with time; 2) determining all non-isomorphic maximum common connected fragments of the T-tree (T-directed tree) which do not change with time. The choice of the primary study of temporal directed trees and trees is justified by the wide range of their practical applications. Effective methods for their solution are proposed. Examples of the solution of the problem for temporal trees and temporal directed trees are given. It is shown that the experimental estimates of the computational complexity of the solution for problems of the temporal directed trees and the temporal trees.

Keywords

[1] M. A. Aizerman, L. A. Gusev, S. V. Petrov, and I. M.Smirnova, A dynamic approach t analysis of structures represented as graphs (fundamentals of graph dynamics). I, Avtom. i Telemekhanika, 7 (1977) 135–151.
[2] P. J. Bramsen, Doing Time: inducing temporal graphs. master thesis of engineering in computer science and engineering, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2006.
[3] D. Braha and Y. Bar-Yam. Time-dependent complex networks: dynamic centrality, dynamic motifs, and cycles of social interactions, Gross T., Sayama H. (eds) Adaptive Networks. Understanding Complex Systems. Springer, Berlin, Heidelberg, 2009, pp: 39-50.
[4] K. P. Raj and J. Saram¨aki, Path lengths, correlations, and centrality in temporal networks, Phys. p 016105, 84(1) (2011) 16105.
[5] N. Santoro, W. Quattrociocchi, P. Flocchini, A. Casteigts and F. Amblard, Time-varying graphs and social network analysis: temporal indicators and metrics, arXiv Prepr.(2011) arXiv1102.0629.
[6] V. V. Kokhov, Problems and methods of analysis of similarity of temporal digraphs, Proceedings of Fourteenth National Conference on Artificial Intelligence KII-2014, Kazan, October 24-27, (2014), pp. 155-163.
[7] H. A. Jonassen, Configuration management principles and practice, Addison-Wesley Pub Co. 2002.
[8] V. Kostakos, Temporal graphs Physica A: Stat. Mech. Appl. 388(6) (2009) 1007–1023.
[9] J. Tang, M. Musolesi, C. Mascolo, and V. Latora, Temporal distance metrics for social network analysis, In Proceedings of the 2nd ACM workshop on Online social networks, 2009, pp. 31-36.
[10] C. C. Aggarwal, and H. Wang, Managing and mining graph data, Springer, New York, 2010.
[11] S. Fortunato, Community detection in graphs, Phys. Rep. 486(3-5) (2010) 75–174.
[12] P. Basu, A. Bar-Noy, R. Ramanathan, and M.P. Johnson, Modeling and analysis of time-varying graphs, arXiv preprint arXiv:1012.0260.(2010).
[13] P. Holme and J. Saramaki, Temporal networks. Phys. Rep., 519(3) (2012) 97–125.
[14] G. Ghoshal, and A.L. Barabasi, Ranking stability and super-stable nodes in complex networks, Nature Commun. 2(1) (2011) 1–7.
[15] F. Kuhn, and R. Oshman, Dynamic networks: models and algorithms, ACM SIGACT News, 42(1) (2011) 82–96.
[16] M. R. Gary, and D.S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, 1979.
[17] A. R. Ibrahim, Development of methods and software for analyzing the similarity of acyclic structures, Ph.D. Thesis in Technical Science, National Research University “MPEI”, Russ., Moscow, https://translate.google.ru/translatehl=en&sl=ru&u=https://www.dissercat.com/content/razrabotkametodov-i-programmnykh-sredstv-dlya-analiza skhodstva-atsiklicheskikh-struktur&prev=search&pto=aue
[18] V. A. Kokhov, S. A. Gorshkov, A. R. Ibrahim and M. R. Jasim, Asni graph-models workshop: subsystem of structural spectral analysis of trees, Proc. Int. Conf. ”Information Tools Technol. MFI ”Network journal. Theory Pract. Russ., Moscow, 9(2) (2006) 104–108.
 
International Journal of Nonlinear Analysis and Applications
Volume 12, Issue 1
May 2021
Pages 111-118
  • Receive Date: 08 February 2020
  • Revise Date: 05 October 2020
  • Accept Date: 13 October 2020