Počet záznamů: 1
The non-positive circuit weight problem in parametric graphs: A solution based on dioid theory
- 1.
SYSNO ASEP 0556580 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název The non-positive circuit weight problem in parametric graphs: A solution based on dioid theory Tvůrce(i) Zorzenon, D. (DE)
Komenda, Jan (MU-W) RID, SAI, ORCID
Raisch, J. (DE)Zdroj.dok. Discrete Applied Mathematics. - : Elsevier - ISSN 0166-218X
Roč. 315, July 15 (2022), s. 56-70Poč.str. 15 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova parametric graphs ; non-positive circuit weight ; max-plus algebra Vědní obor RIV BA - Obecná matematika Obor OECD Automation and control systems CEP GC19-06175J GA ČR - Grantová agentura ČR LTAUSA19098 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy Způsob publikování Omezený přístup Institucionální podpora MU-W - RVO:67985840 UT WOS 000911474000001 EID SCOPUS 85127340713 DOI 10.1016/j.dam.2022.03.008 Anotace 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). Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2023 Elektronická adresa https://doi.org/10.1016/j.dam.2022.03.008
Počet záznamů: 1