On the use of graphs in discrete tomography
BP2-STS
- de Werra, Dominique EPFL, Lausanne, Switzerland
- Costa , Marie-Christine CNAM, Paris, France
- Picouleau, Christophe CNAM, Paris, France
- Ries, Bernard ORCID EPFL, Lausanne, Switzerland
- 2008
Published in:
- 4OR. - Springer Science and Business Media LLC. - 2008, vol. 6, no. 2, p. 101-123
Discrete tomography
Complete bipartite graph
Edge coloring
Timetabling
Constrained coloring
Scheduling
English
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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- Rights reserved
- Open access status
- green
- Identifiers
-
- DOI 10.1007/s10288-008-0077-5
- ISSN 1619-4500
- Persistent URL
- https://folia.unifr.ch/unifr/documents/322635
Statistics
Document views: 13
File downloads:
- discretetomographycopy.pdf: 24