International Journal of Nonlinear Analysis and Applications

Classification of problems of determining the maximum common fragments for two structures of a temporal digraph

Document Type : Research Paper

Author

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

Abstract

A new approach is proposed for classifying the problems of determining the maximum common fragments (MCF) for two connected structures included in the T-digraph, based on the type of the maximum common fragment. A tree of classification the problems of determining the maximum common fragments (MCF) for two structures tiG,tjG(MCF(tiG,tjG)) included in the T-digraph is proposed. Examples are given for a digraph tG with three types of its fragments (parts), and for five connectivity types of digraphs. The formulation of six basic problems of determining the maximum common fragments (MCF) for two connected structures included in the T-digraph is given. A classification is proposed for an isomorphic embedding of a digraph into another.

Keywords

[1] M.A. Aizerman, L.A. Gusev, S.V. Petrov and I.M. Smirnova, A dynamic approach to analysis of structures represented as graphs (fundamentals of graph dynamics), I. Avtomat. Telemekh. 7 (1977) 135-151.
[2] F. Kuhn and R. Oshman, Dynamic networks: models and algorithms, ACM SIGACT News 42(1) (2011) 82-96.
[3] V.A. Kokhov, Two approaches to determining similarity of two digraphs, J. Comput. Syst. Sci. Int. 51(5) (2012) 695-714.
[4] A.R. Ibrahim, A method for analyzing the problem of determining the maximum common fragments of temporal directed tree, that do not change with time, Int. J. Nonlinear Anal. Appl. 12(1) (2021) 111-118.
[5] P. Holme and J. Saramki, Temporal networks, Phys. Rep. 519(3) (2012) 97-125.
[6] A. Casteigts, P. Flocchini, W. Quattrociocchi and N. Santoro, Time-varying graphs and dynamic networks, Int. J. Parallel Emerg. Distrib. Syst. 27(5) (2012) 387-408.
[7] P.J. Bramsen, Doing time: Inducing temporal graphs, Doctoral dissertation, Massachusetts Institute of Technology, 2006.
[8] D. Braha and Y. Bar-Yam, Time-dependent complex networks: Dynamic centrality, dynamic motifs, and cycles of social interactions, In Adaptive Networks, Springer, Berlin, Heidelberg, 2009, pp. 39-50.
[9] N. Santoro, W. Quattrociocchi, P. Flocchini, A. Casteigts and F. Amblard, Time-varying graphs and social network analysis: Temporal indicators and metrics, arXiv preprint arXiv:1102.0629 (2011).
[10] A. M. J. Hass, Configuration management principles and practice, Addison-Wesley Professional, (2003).
[11] V. Kostakos, Temporal graphs, Phys. A: Statist. Mech. Appl. 388(6) (2009) 1007-1023.
[12] J. Tang, M. Musolesi, C. Mascolo and V. Latora, Temporal distance metrics for social network analysis, Proc. 2nd ACM workshop on Online social networks, 2009, pp. 31-36.
[13] P. Basu, A. Barney, M.P. Johnson and R. Ramanathan, Modeling and analysis of time-varying graphs, arXiv Prepr arXiv10120260, (2010).
[14] A. Paranjape, A.R. Benson and J. Leskovec, Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, WSDM17, 2017.
[15] D. Kempe, J. Kleinberg and A. Kumar, Connectivity and inference problems for temporal networks, J. Comput. Syst. Sci. 64(4) (2002) 820-842.
[16] V. Campos, R. Lopes, A. Marino and A. Silva, Edge-Disjoint branchings in temporal graphs, Int. Workshop Combin. Algorithms, Springer, Cham, 2020, pp. 112-125.
[17] V. Lozin, Graph Theory Notes, 2015, available at https://www.khoury.northeastern.edu/home/vip/teach/DiscreteMath/html/Honors/Graph-Theory-notes.pdf.
[18] T.V. Shinkarenko, R.G. Smirnov and A.V. Beloshitskiy, Studying the organizational structure effectiveness on the basis of internal communication analysis, Upravlenets 11(2) (2020) 27-40.
[19] K. Cai and H. Ishii, Average consensus on general strongly connected digraphs, Automatica 48(11) (2012) 2750-2761.
[20] A. Frank, How to make a digraph strongly connected, Combinatorica 1(2) (1981) 145-153.
[21] F. Harary and R.Z. Norman, Some properties of line digraphs, Rend. Circ. Mate. Palermo 9(2) (1960) 161-168.
[22] R.A. Brualdi, F. Harary and Z. Miller, Bigraphs versus digraphs via matrices, J. Graph Theory 4(1) (1980) 51-73.
[23] J.J.P. Veerman and E. Kummel, Diffusion and consensus on weakly connected directed graphs, Linear Alg. Appl. 578 (2019) 184-206.
International Journal of Nonlinear Analysis and Applications
Volume 12, Issue 1
May 2021
Pages 869-875
  • Receive Date: 26 November 2020
  • Revise Date: 07 March 2021
  • Accept Date: 13 March 2021