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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F22%3A00556580" target="_blank" >RIV/67985840:_____/22:00556580 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.dam.2022.03.008" target="_blank" >https://doi.org/10.1016/j.dam.2022.03.008</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2022.03.008" target="_blank" >10.1016/j.dam.2022.03.008</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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).

Název v anglickém jazyce

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

Popis výsledku anglicky

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).

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

20205 - Automation and control systems

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

1872-6771

Svazek periodika

315

Číslo periodika v rámci svazku

July 15

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

15

Strana od-do

56-70

Kód UT WoS článku

000911474000001

EID výsledku v databázi Scopus

2-s2.0-85127340713