On the uncapacitated K-commodity network design problem with zero flow-costs

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.