Reduction from three-dimensional discrete tomography to multicommodity flow problem
The reduction from two-dimensional-discrete tomography to max-flow problem is well-known [Gale, A theorem on flows in networks, Pacific J. Math. 7 (1957) 1073-1082]. This approach is based on the natural correspondence between two-dimensional lattices and bipartite graphs. We extend this result in dimension 3 by reducing three-dimensional discrete tomography to multicommodity flow problems. Two reductions are presented, one considering discrete tomography with multisets while the other one works with sets. (c) 2005 Elsevier B.V. All rights reserved.
multiset flow-max problem integer multicommodity flow problem