In this paper, we consider the following problem: given a layered network including a set of messages, each of which must be transmitted from a source to a sink node, what is the sequence of moves from one node to another which minimizes the total completion time? We first show that the general problem is NP-complete for both fixed and variable path routing (thus the scheduling problem for more realistic networks with cycles must be considered computationally intractable). We then consider several restrictions which admit polynomia time algorithms.

MINIMUM-DELAY SCHEDULES IN LAYERED NETWORKS / D.P. BOVET; P. CRESCENZI. - In: ACTA INFORMATICA. - ISSN 0001-5903. - STAMPA. - 28:(1991), pp. 453-461. [10.1007/BF01178583]

MINIMUM-DELAY SCHEDULES IN LAYERED NETWORKS

CRESCENZI, PIERLUIGI
1991

Abstract

In this paper, we consider the following problem: given a layered network including a set of messages, each of which must be transmitted from a source to a sink node, what is the sequence of moves from one node to another which minimizes the total completion time? We first show that the general problem is NP-complete for both fixed and variable path routing (thus the scheduling problem for more realistic networks with cycles must be considered computationally intractable). We then consider several restrictions which admit polynomia time algorithms.
1991
28
453
461
D.P. BOVET; P. CRESCENZI
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/205996
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact