Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

A polynomial algorithm for minDSC on a subclass of series Parallel graphs

Salim Achouri;  Timothée Bossart;  Alix Munier-Kordon — 2009

RAIRO - Operations Research

The aim of this paper is to show a polynomial algorithm for the problem minimum directed sumcut for a class of series parallel digraphs. The method uses the recursive structure of parallel compositions in order to define a dominating set of orders. Then, the optimal order is easily reached by minimizing the directed sumcut. It is also shown that this approach cannot be applied in two more general classes of series parallel digraphs.

Scheduling an interval ordered precedence graph with communication delays and a limited number of processors

Alix Munier Kordon;  Fadi Kacem;  Benoît Dupont de Dinechin;  Lucian Finta — 2013

RAIRO - Operations Research - Recherche Opérationnelle

We consider the scheduling of an interval order precedence graph of unit execution time tasks with communication delays, release dates and deadlines. Tasks must be executed by a set of processors partitioned into classes; each task requires one processor from a fixed class. The aim of this paper is to study the extension of the Leung–Palem–Pnueli (in short LPP) algorithm to this problem. The main result is to prove that the LPP algorithm can be extended to dedicated processors and monotone communication...

Page 1

Download Results (CSV)