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

DOI10.1016/j.dam.2022.03.008zbMath1491.90177arXiv2102.12264OpenAlexW4226019285MaRDI QIDQ2133400

Jan Komenda, Davide Zorzenon, Jörg Raisch

Publication date: 29 April 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.12264

zbMATH Keywords

max-plus algebraformal languagesdioid theorynon-positive circuit weightP-time event graphsparametric graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weighted digraphs and tropical cones
• Parametric shortest path algorithms with an application to cyclic staffing
• A characterization of the minimum cycle mean in a digraph
• A parametric critical path problem and an application for cyclic scheduling
• Mathematical problems for the next century
• A note on tropical linear and integer programs
• Abstract tropical linear programming
• Steady state analysis of timed event graphs with time window constraints
• Maximum-Minimum Sätze über Graphen
• Max-linear Systems: Theory and Algorithms
• Performance evaluation of (max,+) automata
• Analysis of P-time event graphs in (max,+) and (min,+) semirings
• Semirings and Formal Power Series
• Programming Languages and Systems
• Faster parametric shortest path and minimum‐balance algorithms