On a graph coloring problem arising from discrete tomography

An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph $G=(V,E)$ and a family $\mathcal{P}$ of chains $P_i$ together with vectors $h(P_i)=(h_{i}^{1},...,h_{i}^{k})$, one wants to find a partition $V^{1},...,V^{k}$ of $V$ such that for each $P_i$ and each color $j$, $|V^{j}\cap P_i|=h_{i}^{j}$. 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 $V^{1},...,V^{k}$ 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.


Published in:
Networks, 51, 4, 256-267
Year:
2008
Keywords:
Other identifiers:
Laboratories:




 Record created 2006-08-31, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)