Electronic Resource
Springer
Acta informatica
28 (1991), S. 453-461
ISSN:
1432-0525
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01178583
Permalink
| Library |
Location |
Call Number |
Volume/Issue/Year |
Availability |
