All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 6 of 6

Showing per page

Scheduling in the presence of processor networks : complexity and approximation

Vincent Boudet, Johanne Cohen, Rodolphe Giroudeau, Jean-Claude König (2012)

RAIRO - Operations Research

In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule ...

Scheduling in the presence of processor networks : complexity and approximation

Vincent Boudet, Johanne Cohen, Rodolphe Giroudeau, Jean-Claude König (2012)

RAIRO - Operations Research

In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule ...

Some results on complexity of μ-calculus evaluation in the black-box model

Paweł Parys (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We consider μ-calculus formulas in a normal form: after a prefix of fixed-point quantifiers follows a quantifier-free expression. We are interested in the problem of evaluating (model checking) such formulas in a powerset lattice. We assume that the quantifier-free part of the expression can be any monotone function given by a black-box – we may only ask for its value for given arguments. As a first result we prove that when the lattice is fixed, the problem becomes polynomial (the assumption about...

String distances and intrusion detection: Bridging the gap between formal languages and computer security

Danilo Bruschi, Giovanni Pighizzini (2006)

RAIRO - Theoretical Informatics and Applications

In this paper we analyze some intrusion detection strategies proposed in the literature and we show that they represent the various facets of a well known formal languages problem: computing the distance between a string x and a language L. In particular, the main differences among the various approaches adopted for building intrusion detection systems can be reduced to the characteristics of the language L and to the notion of distance adopted. As a further contribution we will also show that from...

Currently displaying 1 – 6 of 6

Page 1