Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Network design with non simultaneous flows
Lucertini M. (ed), Paletta G., Springer-Verlag New York, Inc., New York, NY, 1984. Type: Book (9780387818160)
Date Reviewed: Jun 1 1985

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
Bookmark and Share
 
Combinatorics (G.2.1 )
 
 
Network Architecture And Design (C.2.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Combinatorics": Date
Applied combinatorics with problem solving
Jackson B., Thoro D., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992. Type: Book (9780201129083)
Feb 1 1993
Parallel generation of permutations and combinations
Chen G., Chern M. BIT 26(3): 277-283, 1986. Type: Article
Jul 1 1988
Walsh-spectral test for GFSR pseudorandom numbers
Tezuka S. Communications of the ACM 30(9): 731-735, 1987. Type: Article
Jun 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy