Generalized Path Optimization Problem for a Weighted Digraph over an Additively Idempotent Semiring

Authors

  • Junsheng Duan School of Sciences, Shanghai Institute of Technology, Shanghai, China
  • Dichen Hu School of Sciences, Shanghai Institute of Technology, Shanghai, China

DOI:

https://doi.org/10.15377/2409-5761.2020.07.4

Keywords:

Semiring, Path optimization, Digraph, Incline, Partial order

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

Downloads

Published

2020-11-13

How to Cite

Duan, J., & Hu, D. . (2020). Generalized Path Optimization Problem for a Weighted Digraph over an Additively Idempotent Semiring. Journal of Advances in Applied &Amp; Computational Mathematics, 7(1), 25–31. https://doi.org/10.15377/2409-5761.2020.07.4

Issue

Section

Articles