New transience bounds for max-plus linear systems

DOI10.1016/j.dam.2016.11.003zbMath1354.05092arXiv1209.3342OpenAlexW2560346745MaRDI QIDQ505429

Matthias Függer, Bernadette Charron-Bost, Thomas Nowak

Publication date: 23 January 2017

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

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

zbMATH Keywords

cyclic schedulinglink-reversal algorithmsmax-plus systemsnetwork synchronizerstransience bounds

Mathematics Subject Classification ID

Operations research and management science (90B99) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (6)

On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers ⋮ Local and global robustness with \(q\)-step delay for max-plus linear systems ⋮ Weak CSR expansions and transience bounds in max-plus algebra ⋮ New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank ⋮ Computing periodic request functions to speed-up the analysis of non-cyclic task models ⋮ Computation of the transient in max-plus linear systems via SMT-solving

Cites Work

• Unnamed Item
• An extension of the Dulmage-Mendelsohn theorem
• The index set problem for Boolean (or nonnegative) matrices
• The use of a synchronizer yields the maximum computation rate in distributed networks
• Gaps in the exponent set of primitive matrices
• Dynamic analysis of repetitive decision-free discrete-event processes: The algebra of timed marked graphs and algorithmic issues
• Unzerlegbare, nicht negative Matrizen
• Transience Bounds for Long Walks
• Link Reversal Routing with Binary Link Labels: Work Complexity
• Asymptotic optimality of shortest path routing algorithms
• A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing
• Max-Balancing Weighted Directed Graphs and Matrix Scaling
• Complexity of network synchronization
• Periods of Connected Networks and Powers of Nonnegative Matrices
• Time Complexity of Link Reversal Routing
• Analysis of Link Reversal Routing Algorithms
• On a sharp estimation in the theory of binary relations on a finite set

This page was built for publication: New transience bounds for max-plus linear systems