Article ID Journal Published Year Pages File Type
9657731 Theoretical Computer Science 2005 7 Pages PDF
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,