Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657731 | Theoretical Computer Science | 2005 | 7 Pages |
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
Y. Gerard,