Keywords
Digraph, Incline
Partial order
How to Cite
Abstract
In this paper, a generalized path optimization problem for a weighted digraph (i.e., directed graph) over an additively idempotent semiring was considered. First, the conditions for power convergence of a matrix over an additively idempotent semiring were investigated. Then we proved that the path optimization problem is associated with powers of the adjacency matrix of the weighted digraph. The classical matrix power method for the shortest path problem on the min-plus algebra was generalized to the generalized path optimization problem. The proposed generalized path optimization model encompasses different path optimization problems, including the longest path problem, the shortest path problem, the maximum reliability path problem, and the maximum capacity path problem. Finally, for the four special cases, we illustrate the pictorial representations of the graphs with example data and the proposed method.
References
Fan ZT. Fuzzy Matrix Theory and Applications. Science Press, Beijing 2006.
Qiao Z and Yin J. Fuzzy deep medical diagnostic system: gray relation framework and the guiding functionalities for the professional sports club social responsibility. Journal of Medical Imaging and Health Informatics 2020; 10 (5): 1084- 1090. https://doi.org/10.1166/jmihi.2020.2891
Singh S and Ganie AH. Applications of picture fuzzy similarity measures in pattern recognition, clustering, and MADM. Expert Systems with Applications 2021; 168: Article No. 114264. https://doi.org/10.1016/j.eswa.2020.114264
Du GL, Liang YH, Gao BY, Al-Otaibi S and Li D. A cognitive joint angle compensation system based on self-feedback fuzzy neural network with incremental learning. IEEE Transactions on Industrial Informatics 2021; 17 (4): 2928- 2937. https://doi.org/10.1109/TII.2020.3003940
Zeng W, Xi Y, Yin Q and Guo P. Weighted dual hesitant fuzzy set and its application in group decision making. Neurocomputing, Available online 6 Nov. 2020. https://doi.org/10.1016/j.neucom.2020.07.134
Goyal RK and Kaushal S. Deriving crisp and consistent priorities for fuzzy AHP-based multicriteria systems using nonlinear constrained optimization. Fuzzy Optimization and Decision Making 2018; 17: 195-209. https://doi.org/10.1007/s10700-017-9267-y
Zhang Z, Zheng W, Lam HK, Wen S, Sun F and Xie P. Stability analysis and output feedback control for stochastic networked systems with multiple communication delays and nonlinearities using fuzzy control technique. Applied Mathematics and Computation 2020; 386: Article No. 125374. https://doi.org/10.1016/j.amc.2020.125374
Thomason MG. Convergence of powers of a fuzzy matrix. Journal of Mathematical Analysis and Applications 1977; 57 (2):476-480. https://doi.org/10.1016/0022-247X(77)90274-8
Fan ZT and Cheng QS. A survey on the powers of fuzzy matrices and FBAMs. International Journal of Computational Cognition 2004; 2 (2): 1-25.
Hashimoto H. Convergence of powers of a fuzzy transitive matrix. Fuzzy Sets and Systems 1983; 9 (1-3): 153-160. https://doi.org/10.1016/S0165-0114(83)80015-3
Kim KH and Roush FW. Generalized fuzzy matrices. Fuzzy Sets and Systems 1980; 4 (3): 293-315. https://doi.org/10.1016/0165-0114(80)90016-0
Li JX. An upper bound on indices of finite fuzzy relations. Fuzzy Sets and Systems 1992; 49 (3): 317-321. https://doi.org/10.1016/0165-0114(92)90283-A
Cechlarova K. On the powers of matrices in Bottleneck/Fuzzy algebra. Linear Algebra and its Applications 1996; 246: 97- 111. https://doi.org/10.1016/0024-3795(94)00338-6
Tan Y. On the powers of matrices over a distributive lattice. Linear Algebra and its Applications 2001; 336 (1-3): 1-14. https://doi.org/10.1016/S0024-3795(00)00168-3
Zhang KL. On the nilpotent matrices over D01-lattice. Fuzzy Sets and Systems 2001; 117 (3): 403-406. https://doi.org/10.1016/S0165-0114(98)00270-X
Tan Y. On the eigenproblem of matrices over distributive lattices. Linear Algebra and its Applications. 2003, 374, 87- 106. https://doi.org/10.1016/S0024-3795(03)00550-0
Wu Y, Wang J and Yang Y. Lattice-ordered effect algebras and L-algebras. Fuzzy Sets and Systems 2019, 369: 103-113. https://doi.org/10.1016/j.fss.2018.08.013
Cao ZQ, Kim KH and Roush FW. Incline Algebra and Applications. John Wiley & Sons, New York 1984.
Han SC and Li HX. Indices and periods of incline matrices. Linear Algebra and its Applications 2004; 387: 143-165. https://doi.org/10.1016/j.laa.2004.02.024
Duan JS. The transitive closure, convergence of powers and adjacency of generalized fuzzy matrices. Fuzzy Sets and Systems 2004; 145 (2): 301-311. https://doi.org/10.1016/S0165-0114(03)00165-9
Duan JS. Invertible conditions for matrices over an incline. Advances in Mathematics 2006; 35: 285-288. http://en.cnki.com.cn/Article_en/CJFDTOTALSXJZ200603004.htm
Duan JS, Guo AP, Zhao FX, Xu L and Tang WG. Standard bases of a vector space over a linearly ordered incline. Communications in Algebra 2011; 39 (4): 1404-1412, https://doi.org/10.1080/00927871003738915
Han SC and LI HX. Some conditions for matrices over an incline to be invertible and general linear group on an incline. Acta Mathematica Sinica 2005; 21 (5): 1093-1098. https://doi.org/10.1007/s10114-004-0497-x
Han SC and Li HX. Invertible incline matrices and Cramer's rule over inclines. Linear Algebra and its Applications 2004; 389:121-138. https://doi.org/10.1016/j.laa.2004.03.025
Meenakshi A. Regular matrices over an incline. In: Bapat R, Kirkland S, Prasad K and Puntanen S (Eds). Combinatorial Matrix Theory and Generalized Inverses of Matrices. Springer, India 2013, 183-193. https://doi.org/10.1007/978-81-322-1053-5_16
Han SC and Li HX. The semigroup of incline Hall matrices. Linear Algebra and its Applications 2004; 390: 183-196. https://doi.org/10.1016/j.laa.2004.04.016
Meenakshi AR and Banu PS. On regularity of incline matrices. International Journal of Algebra 2011; 5 (19): 909-924. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.407 .7013
Zhang LM, Qiao LS and Li Y. Invertible incline matrices and ranks of incline matrices. Journal of Shandong University (Natural Science) 2007; 42 (9): 122-126. http://lxbwk.njournal.sdu.edu.cn/EN/Y2007/V42/I9/122
Meenakshi AR and Anbalagan S. On regular elements in an incline. International Journal of Mathematics and Mathematical Sciences 2010; 2010: 1-12. https://doi.org/10.1155/2010/903063
Kim KH and Roush FW. Inclines and incline matrices: a survey. Linear Algebra and its Applications 2004; 379: 457- 473. https://doi.org/10.1016/j.laa.2003.09.009
Kendziorra A and Zumbragel J. Finite simple additively idempotent semirings. Journal of Algebra 2013; 388: 43-64. https://doi.org/10.1016/j.jalgebra.2013.04.023
Gaubert S and Plus M. Methods and applications of (max,+) linear algebra. In: Reischuk R and Morvan M (Eds). STACS 1997, Lecture Notes in Computer Science, Vol. 1200. Springer, Berlin, Heidelberg 1997, 261-282. https://doi.org/10.1007/BFb0023465
Watanabe S, Fukuda A, Segawa E and Sato I. A walk on maxplus algebra. Linear Algebra and its Applications 2020; 598: 29-48. https://doi.org/10.1016/j.laa.2020.03.025
Tan Y. On invertible matrices over antirings. Linear Algebra and its Applications 2007; 423 (2-3): 428-444. https://doi.org/10.1016/j.laa.2007.01.018
Sergeev S. Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes. Linear Algebra and its Applications 2009; 431 (8): 1325-1339. https://doi.org/10.1016/j.laa.2009.04.027
Mohindru P and Pereira R. Orderings on semirings and completely positive matrices. Linear & Multilinear Algebra 2016; 64 (5): 818-833. https://doi.org/10.1080/03081087.2015.1059405
Demetrescu C and Italiano GF. Dynamic shortest paths and transitive closure: Algorithmic techniques and data structures. Journal of Discrete Algorithms 2006; 4 (3): 353-383. https://doi.org/10.1016/j.jda.2005.12.003
Demetrescu C and Italiano GF. Fully dynamic all pairs shortest paths with real edge weights. Journal of Computer and System Sciences 2006; 72 (5): 813-837. https://doi.org/10.1016/j.jcss.2005.05.005
Giudicianni C, Herrera M, Nardo AD, Oliva G and Scala A. The faster the better: On the shortest paths role for near real-time decision making of water utilities. Reliability Engineering & System Safety 2021; 212: Article No. 107589. https://doi.org/10.1016/j.ress.2021.107589
Likaj R, Shala A, Mehmetaj M, Hyseni P and Bajrami X. Application of graph theory to find optimal paths for the transportation problem. IFAC Proceedings Volumes 2013; 46 (8): 235-240. https://doi.org/10.3182/20130606-3-XK-4037.00031
Rusakov VA. Matrices, shortest paths, minimal cuts and Euclidian metric for undirected graphs. Procedia Computer Science 2018; 145: 444-447. https://doi.org/10.1016/j.procs.2018.11.104
Rodriguez-Velazquez JA, Kamisalic A and Domingo-Ferrer J. On reliability indices of communication networks. Computers & Mathematics with Applications 2009; 58 (7): 1433-1440. https://doi.org/10.1016/j.camwa.2009.07.019
Asghari S and Azadi K. A reliable path between target users and clients in social networks using an inverted ant colony optimization algorithm. Karbala International Journal of Modern Science 2017; 3 (3): 143-152. https://doi.org/10.1016/j.kijoms.2017.05.004
Keshavarz E and Khorram E. A fuzzy shortest path with the highest reliability. Journal of Computational and Applied Mathematics 2009; 230 (1): 204-212. https://doi.org/10.1016/j.cam.2008.11.007
Lin MS and Ting CC. Computing the K-terminal reliability of directed path graphs. Information Processing Letters 2015; 115 (10): 773-778. https://doi.org/10.1016/j.ipl.2015.05.005
Zimmermann U. Linear and Combinatorial Optimization in Ordered Algebraic Structures, Annals of Discrete Mathematics 10. Elsevier, Netherlands 1981.
Gondran M and Minoux M. Graphs, Dioids and Semirings. Springer, New York 2008.
Abu-Bekr J, Chikalov I, Hussain S and Moshkov M. Sequential optimization of paths in directed graphs relative to different cost functions. Procedia Computer Science 2011; 4: 1272- 1277. https://doi.org/10.1016/j.procs.2011.04.137
Li J, Sun P and Hu Y. Traffic modeling and optimization in datacenters with graph neural network. Computer Networks 2020; 181: Article No. 107528. https://doi.org/10.1016/j.comnet.2020.107528
Gould V, Johnson M and Naz M. Matrix semigroups over semirings. International Journal of Algebra and Computation. 2020; 30 (2): 267-337. https://doi.org/10.1142/S0218196720500010
Araujo J, Campos VA, Maia AK, Sau I and Silva A. On the complexity of finding internally vertex-disjoint long directed paths. Algorithmica 2020; 82 (6): 1616-1639. https://doi.org/10.1007/s00453-019-00659-5
Liu XJ, Machado RA and Milenkovic O. Directed intersection representations and the information content of digraphs. IEEE Transactions on Information Theory 2021; 67 (1): 347-357. https://doi.org/10.1109/TIT.2020.3033168
Woods BD and Punnen AP. A class of exponential neighbourhoods for the quadratic travelling salesman problem. Journal of Combinatorial Optimization 2020; 40: 303- 332. https://doi.org/10.1007/s10878-020-00588-y
Magnouche Y and Martin S. Most vital vertices for the shortest s-t path problem: complexity and Branch-and-Cut algorithm. Optimization Letters 2020; 14 (8): 2039-2053. https://doi.org/10.1007/s11590-019-01527-5
Brinzei N and Aubry JF. Graphs models and algorithms for reliability assessment of coherent and non-coherent systems. Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability 2018; 232 (2): 201-215. https://doi.org/10.1177/1748006X17744381
Kuperman O and Vardi G. Flow logic. Logical Methods in Computer Science 2019; 15 (4): Article No. 9. https://doi.org/10.23638/LMCS-15(4:9)2019
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Copyright (c) 2020 Journal of Advances in Applied & Computational Mathematics