An Algorithm of Plus-Closures of Loop-Nonnegative Matrices over Idempotent Semirings and its Applications

摘要：

　　Tojudge the ioop-nonnegativity of a matrix A over an idempotent semiring and compute the plus-closure of A when it is loop-nonnegative,a Plus_Closure_of_Matrix algorithm of complexity O(n3) is constructed and proved.As a generalization of Floyd algorithm,Warshall algorithm as well as Gauβ-Jordan Elimination algorithm on idempotent semirings,this algorithm can also be used to solve some Algebraic Path Problems,Shortest Path Problems and the transitive closures of matrices over idempotent semirings even if the idempotent semirings have no completeness and closeness.

关键词： Idempotent semiring Loop-nonnegative matrix Plus-closure Plus_Closure_of_Matrix Algorithm

作者: Wang Zhixi Wang Yana Hu Binliang Liu Yu

作者单位: School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan 41120 Colleges of Electromechanical Engineering,Hunan University of Science and Technology,Xiangtan 411201 School of Vocational and Technical,Nanning College of Vocational and Technical,Nanning 530000,Guangx

会议类型: 国际会议

会议名称: 2013 2nd International Conference on Computer Science and Electronics Engineering(ICCSEE2013)(2013年第二届计算机科学与电子工程国际会议)

会议地点: 杭州

会议语种:英文

页码: 2713-2717

在线出版日期: 2013-03-22（万方平台首次上网日期，不代表论文的发表时间）