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

Abstract

Let us 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}\cup \{-\infty \}$. In this paper, we design an algorithm that solves the Non-positive Circuit weight Problem (NCP) on this class of parametric graphs, which consists in finding 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 $\mathcal{O}(n^4)$ (where $n$ is the number of nodes in the graph).

25 pages, 4 figures, revised version. Proof of Proposition 6 corrected

References in corpus (1)

• Periodic trajectories in P-time event graphs and the non-positive circuit weight problem

Cited by in corpus (3)

• Switched max-plus linear-dual inequalities: cycle time analysis and applications
• Periodic trajectories in P-time event graphs and the non-positive circuit weight problem
• Switched Max-Plus Linear-Dual Inequalities: Application in Scheduling of Multi-Product Processing Networks