Affiner les résultats

Type de document

Collection spécifique

Langue

Université de Fribourg

On a graph coloring problem arising from discrete tomography

Bentz, Cédric ; Costa, Marie-Christine ; de Werra, Dominique ; Picouleau, Christophe ; Ries, Bernard

In: Networks, 2008, vol. 51, no. 4, p. 256-267

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...