Computing Reviews

Network design with non simultaneous flows
Lucertini M. (ed), Paletta G., Springer-Verlag New York, Inc.,New York, NY,1984.Type:Book
Date Reviewed: 06/01/85

A basic problem in network design is capacity assignment, in which one must determine the minimum total edge capacity required to support a flow from a source node to a set of specified sinks. A demand vector specifies the required flow at each sink. This paper examines a variant of the problem in which a number of different demand vectors are given; the designed network is required to meet each of the demand vectors. (However, it does not have to meet any two simultaneously.) For this variant, the optimal solution is shown to be the sum of certain paths and cycles, which can easily be found. Computational complexity is dealt with in the paper only briefly; the authors conclude that their method is exponential in the number of sinks, but polynomial for a fixed number of sinks.

Reviewer:  Charles Colbourn Review #: CR109091

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy