On a graph coloring problem arising from discrete tomography
- Bentz, Cédric CNAM, France
- Costa, Marie-Christine CNAM, France
- de Werra, Dominique EPFl, Switzerland
- Picouleau, Christophe CNAM, France
- Ries, Bernard EPFL, Switzerland
-
2008
Published in:
- Networks. - 2008, vol. 51, no. 4, p. 256-267
English
An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph G = (V,E) and a family equation image of chains Pi together with vectors h(Pi) = (h1, . . . , hik), one wants to find a partition V1,…,Vk of V such that for each Pi and each color j, |Vj ∩ Pi| = hij. An interpretation in terms of scheduling is presented. We consider special cases of graphs and identify polynomially solvable cases; general complexity results are established in this case and also in the case where V1,...Vk is required to be a proper vertex k-coloring of G. Finally, we examine also the case of (proper) edge k-colorings and determine its complexity status.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
-
License undefined
- Identifiers
-
- RERO DOC 326909
- DOI 10.1002/net.20218
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307833
Export to…
Statistics
Document views: 226
File downloads:
- Document: 427