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

0556580 - MÚ 2023 RIV NL eng J - Journal Article
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
R&D Projects: GA ČR(CZ) GC19-06175J; GA MŠMT(CZ) LTAUSA19098
Institutional support: RVO:67985840
Keywords : parametric graphs * non-positive circuit weight * max-plus algebra
OECD category: Automation and control systems
Impact factor: 1.1, year: 2022
Method of publishing: Limited access
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).
Permanent Link: http://hdl.handle.net/11104/0330749