The non-positive circuit weight problem in parametric graphs: A solution based on dioid theory

0556580 - MÚ 2023 RIV NL eng J - Článek v odborném periodiku
Zorzenon, D. - Komenda, Jan - Raisch, J.
The non-positive circuit weight problem in parametric graphs: A solution based on dioid theory.
Discrete Applied Mathematics. Roč. 315, July 15 (2022), s. 56-70. ISSN 0166-218X. E-ISSN 1872-6771
Grant CEP: GA ČR(CZ) GC19-06175J; GA MŠMT(CZ) LTAUSA19098
Institucionální podpora: RVO:67985840
Klíčová slova: parametric graphs * non-positive circuit weight * max-plus algebra
Obor OECD: Automation and control systems
Impakt faktor: 1.1, rok: 2022
Způsob publikování: Omezený přístup
https://doi.org/10.1016/j.dam.2022.03.008

We consider a parametric weighted directed graph in which every $arc (j, i)$ has weight of the form $w((j, i)) = max(P_{ij}+lambda, I{ij}-lambda,C_{ij} )$, where $lambda$ is a real parameter, and P, I and C are arbitrary square matrices with elements in $mathbb{R} cap { -infty}$. An algorithm is proposed that solves the Non-positive Circuit weight Problem (NCP) on this class of parametric graphs, which consists in fi nding all values of $lambda$ such that the graph does not contain circuits with positive weight. This problem, which generalizes other instances of the NCP previously investigated in the literature, has applications in the consistency analysis of a class of discrete-event systems called P-time event graphs. The proposed algorithm is based on max-plus algebra and formal languages, and improves the worst-case complexity of other existing approaches, achieving strongly polynomial time complexity $O(n^4)$ (where n is the number of nodes in the graph).
Trvalý link: http://hdl.handle.net/11104/0330749