Complexity results for weighted timed event graphs

DOI10.1016/j.disopt.2010.03.006zbMath1242.90279OpenAlexW2066896771MaRDI QIDQ429654

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)

Related Items (1)

An improved approach for marking optimization of timed weighted marked graphs

Uses Software

• SPIN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A sufficient condition for the liveness of weighted event graphs
• Minimizing place capacities of weighted event graphs for enforcing liveness
• A characterization of the minimum cycle mean in a digraph
• A study of the cyclic scheduling problem on parallel processors
• Marking optimization of weighted marked graphs
• On scheduling cycle shops: Classification, complexity and approximation
• Minimizing buffer requirements under rate-optimal schedule in regular dataflow networks
• Marked directed graphs
• A Theorem on n-Coloring the Points of a Linear Graph
• Optimisation of invariant criteria for event graphs
• Throughput-Buffering Trade-Off Exploration for Cyclo-Static and Synchronous Dataflow Graphs
• Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing
• Firing rate optimization of cyclic timed event graphs by token allocations

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