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 Next

Displaying 1 – 20 of 182

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 ...

Selected multicriteria shortest path problems: an analysis of complexity, models and adaptation of standard algorithms

Zbigniew Tarapata (2007)

International Journal of Applied Mathematics and Computer Science

The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multi-objective shortest path (MOSP) problems is given. Different models of MOSP problems are discussed in detail. Methods of solving the formulated optimization problems are presented. An analysis of the complexity of the presented methods and ways of adapting of classical algorithms for solving multiobjective shortest path problems are described. A comparison of the effectiveness...

Self-affine fractals of finite type

Christoph Bandt, Mathias Mesing (2009)

Banach Center Publications

In the class of self-affine sets on ℝⁿ we study a subclass for which the geometry is rather tractable. A type is a standardized position of two intersecting pieces. For a self-affine tiling, this can be identified with an edge or vertex type. We assume that the number of types is finite. We study the topology of such fractals and their boundary sets, and we show how new finite type fractals can be constructed. For finite type self-affine tiles in the plane we give an algorithm which decides whether...

Self-reducibility structures and solutions of NP problems.

José L. Balcázar Navarro (1989)

Revista Matemática de la Universidad Complutense de Madrid

Using polynomial time self-reducibility structures, we characterize certain helping notions, show how the characterization provides the main tool for the proof of known relationships between decisional and functional NP-complete problems, and extend this relationships to the case of optimization NP-complete problems.

Self-replication processes in nanosystems of informatics

Stefan Węgrzyn, Ryszard Winiarczyk, Lech Znamirowski (2003)

International Journal of Applied Mathematics and Computer Science

Recent research on the nanotechnological processes of molecular products and object synthesis as well as research on the nanosystems of informatics, stimulates the development of technical systems of informatics. Until now, they have been used mainly for computational tasks when, similarly to biological organisms, they allowed the development of self-replicating products and complete objects. One can focus here on the model of a circulation of materials, information and energy in a biological cell,...

Self-reproducing pushdown transducers

Alexander Meduna, Luboš Lorenc (2005)

Kybernetika

After a translation of an input string, x , to an output string, y , a self- reproducing pushdown transducer can make a self-reproducing step during which it moves y to its input tape and translates it again. In this self- reproducing way, it can repeat the translation n -times for any n ≥ 1 . This paper demonstrates that every recursively enumerable language can be characterized by the domain of the translation obtained from a self- reproducing pushdown transducer that repeats its translation no more than...

Semantics of value recursion for monadic input/output

Levent Erkök, John Launchbury, Andrew Moran (2002)

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

Monads have been employed in programming languages for modeling various language features, most importantly those that involve side effects. In particular, Haskell’s IO monad provides access to I/O operations and mutable variables, without compromising referential transparency. Cyclic definitions that involve monadic computations give rise to the concept of value-recursion, where the fixed-point computation takes place only over the values, without repeating or losing effects. In this paper, we...

Semantics of value recursion for Monadic Input/Output

Levent Erkök, John Launchbury, Andrew Moran (2010)

RAIRO - Theoretical Informatics and Applications

Monads have been employed in programming languages for modeling various language features, most importantly those that involve side effects. In particular, Haskell's IO monad provides access to I/O operations and mutable variables, without compromising referential transparency. Cyclic definitions that involve monadic computations give rise to the concept of value-recursion, where the fixed-point computation takes place only over the values, without repeating or losing effects. In this paper,...

Currently displaying 1 – 20 of 182

Page 1 Next