On the multi‐commodity flow problem in certain planar directed networks
Hiroshi Nagamochi, Toshihide Ibaraki, Toshiharu Hasegawa · Electronics and Communications in Japan (Part I Communications) · 1988
Abstract This paper introduces the concept of capacity balance (CB) to show that multicommodity flow problems for classes CB and CS (capacity semibalanced) directed networks have efficient graph‐theoretic algorithms. In a wide variety of applications, multicommodity flows are used to represent many important problems. Such applications include the assignment of traffic in roads or communication networks, and routing in VLSI design. For these networks it is possible to develop polynomial time graph‐theoretic algorithms. It is shown that the integral flow property holds for CB, and class CS networks, which are an extension of CB, are considered. As a special case, this class contains a certain multiterm, multistage production scheduling problem [3]. Its importance in practical applications is shown.