Complexity results for weighted timed event graphs

DOI10.1016/J.DISOPT.2010.03.006zbMATH Open1242.90279OpenAlexW2066896771MaRDI QIDQ429654FDOQ429654

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

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

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)

Cites Work

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

Cited In (12)

• Cyclic scheduling for the synthesis of embedded systems
• Title not available (Why is that?)
• Observability of extended timed event graph
• 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

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)