Max‐flow min‐cut theorem for the multicommodity flows in certain planar directed networks
Hiroshi Nagamochi, Toshihide Ibaraki · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1989
Abstract Classes CB, CS and CU have been found as the classes of networks, for which there exist efficient graph‐theoretical algorithms for the multicommodity flow problem on the directed network. This paper shows that the max‐flow min‐cut theorem holds for classes CB and CS. In other words, in those networks, if the multicommodity flow is not feasible, there always exists a cut for a source‐and‐sink pair, indicating the unfeasibility of the flow. For class CU, an example has already been presented where the max‐flow min‐cut theorem does not hold.