The network synthesis problem in a cycle

The network synthesis problem is to design an undirected network with a minimum total construction cost which non-simultaneously satisfies given flow requirements between pairs of nodes. This well-known problem was introduced by Gomory and hu who formulated it as a very large linear program and solved it by a method similar to column generation. The paper provides an efficient algorithm for this problem when the underlying graph is a cycle.