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 $(M C F)$ 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 $(M C F)$ for two structures $t_{i} G, t_{j} G\left(M C F\left(t_{i} G, t_{j} G\right)\right)$ included in the $T$-digraph is proposed. Examples are given for a digraph $t G$ 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