Journal article

On a graph coloring problem arising from discrete tomography

Show more…
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.
Faculté des sciences économiques et sociales
Département d'informatique
  • English
Computer science
License undefined
Persistent URL

Document views: 12 File downloads:
  • paths-rero.pdf: 2