Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering (ICCSEE 2013)

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

Authors
Zhixi Wang, Yana Wang, Binliang Hu, Yu Liu
Corresponding Author
Zhixi Wang
Available Online March 2013.
DOI
10.2991/iccsee.2013.676How to use a DOI?
Keywords
Idempotent semiring, Loop-nonnegative matrix, Plus-closure, Plus_Closure_of_Matrix Algorithm
Abstract

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.

Copyright
© 2013, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering (ICCSEE 2013)
Series
Advances in Intelligent Systems Research
Publication Date
March 2013
ISBN
978-90-78677-61-1
ISSN
1951-6851
DOI
10.2991/iccsee.2013.676How to use a DOI?
Copyright
© 2013, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

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 (ICCSEE 2013)
PB  - Atlantis Press
SP  - 2712
EP  - 2716
SN  - 1951-6851
UR  - https://doi.org/10.2991/iccsee.2013.676
DO  - 10.2991/iccsee.2013.676
ID  - Wang2013/03
ER  -