On the use of graphs in discrete tomography |
| |
Authors: | Dominique de Werra Marie-Christine Costa Christophe Picouleau Bernard Ries |
| |
Institution: | (1) ROSE, Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland;(2) CEDRIC CNAM, Paris, France |
| |
Abstract: | In this tutorial paper, we consider the basic image reconstruction problem which stems from discrete tomography. We derive
a graph theoretical model and we explore some variations and extensions of this model. This allows us to establish connections
with scheduling and timetabling applications. The complexity status of these problems is studied and we exhibit some polynomially
solvable cases. We show how various classical techniques of operations research like matching, 2-SAT, network flows are applied
to derive some of these results.
|
| |
Keywords: | Discrete tomography Complete bipartite graph Edge coloring Timetabling Constrained coloring Scheduling |
本文献已被 SpringerLink 等数据库收录! |