Complexity results for weighted timed event graphs

DOI10.1016/J.DISOPT.2010.03.006MaRDI QIDQ429654zbMATH OpenOpenAlexFDO

Authors Olivier Marchetti, Alix Munier-Kordon

Publication date 20 June 2012

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2010.03.006

zbMATH Keywords

complexityapproximation algorithmthroughputbuffer requirementweighted timed event graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 1070400
• scientific article; zbMATH DE number 1836370
• Minimizing place capacities of weighted event graphs for enforcing liveness
• Some optimization problems for timed marked graphs
• scientific article; zbMATH DE number 4106272

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3722109 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 563124 (Why is no real title available?)
• scientific article; zbMATH DE number 4189459 (Why is no real title available?)
• A Theorem on n-Coloring the Points of a Linear Graph
• A characterization of the minimum cycle mean in a digraph
• A study of the cyclic scheduling problem on parallel processors
• A sufficient condition for the liveness of weighted event graphs
• Firing rate optimization of cyclic timed event graphs by token allocations
• Marked directed graphs
• Marking optimization of weighted marked graphs
• Minimizing buffer requirements under rate-optimal schedule in regular dataflow networks
• Minimizing place capacities of weighted event graphs for enforcing liveness
• On scheduling cycle shops: Classification, complexity and approximation
• Optimisation of invariant criteria for event graphs
• Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing
• Throughput-Buffering Trade-Off Exploration for Cyclo-Static and Synchronous Dataflow Graphs

Cited in

(12)

• Observability of extended timed event graph
• Cyclic scheduling for the synthesis of embedded systems
• scientific article; zbMATH DE number 4189459 (Why is no real title available?)
• Allocating resources of weighted T-system for adaptive behaviour
• The non-positive circuit weight problem in parametric graphs: a solution based on dioid theory
• Steady state analysis of timed event graphs with time window constraints
• A sufficient condition for the liveness of weighted event graphs
• Minimizing place capacities of weighted event graphs for enforcing liveness
• An improved approach for marking optimization of timed weighted marked graphs
• Max-plus algebraic description of evolutions of weighted timed event graphs
• An algebraic model for performance evaluation of timed event multigraphs
• Analysis of P-time event graphs in (max,+) and (min,+) semirings

Describes a project that uses

Uses Software

• SPIN

This page was built for publication: Complexity results for weighted timed event graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q429654)