On the uncapacitated K-commodity network design problem with zero flow-costs
Document Type
Article
Publication Title
Naval Research Logistics
Abstract
Extending Sastry's result on the uncapacitated two-commodity network design problem, we completely characterize the optimal solution of the uncapacitated K-commodity network design problem with zero flow costs for the case when K = 3. By solving a set of shortest-path problems on related graphs, we show that the optimal solutions can be found in O(n3) time when K = 3, where n is the number of nodes in the network. The algorithm depends on identifying a list of "basic patterns"; the number of basic patterns grows exponentially with K. We also show that the uncapacitated K-commodity network design problem can be solved in O(n3) time for general K if K is fixed; otherwise, the time for solving the problem is exponential. © 2004 Wiley Periodicals, Inc.
DOI Link
Publication Date
1-4-2004
Publisher
Wiley
Volume
Vol.51
Issue
Iss.8
Recommended Citation
Ng, Ada Suk-fung; Sastry, Trilochan; Leung, Janny M Y; and Cai, X Q, "On the uncapacitated K-commodity network design problem with zero flow-costs" (2004). Faculty Publications. 1134.
https://research.iimb.ac.in/fac_pubs/1134
