An Algorithm of Plus-Closures of Loop-Nonnegative Matrices over Idempotent Semirings and its Applications
Zhixi Wang, Yana Wang, Binliang Hu, Yu Liu
Available Online March 2013.
- https://doi.org/10.2991/iccsee.2013.676How to use a DOI?
- Idempotent semiring, Loop-nonnegative matrix, Plus-closure, Plus_Closure_of_Matrix Algorithm
- To judge the loop-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 (n) 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.
- Open Access
- This is an open access article distributed under the CC BY-NC license.
Cite this article
TY - CONF AU - Zhixi Wang AU - Yana Wang AU - Binliang Hu AU - Yu Liu PY - 2013/03 DA - 2013/03 TI - An Algorithm of Plus-Closures of Loop-Nonnegative Matrices over Idempotent Semirings and its Applications BT - Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering PB - Atlantis Press SP - 2712 EP - 2716 SN - 1951-6851 UR - https://doi.org/10.2991/iccsee.2013.676 DO - https://doi.org/10.2991/iccsee.2013.676 ID - Wang2013/03 ER -