Colored-independence on Paths

摘要

We consider a storage/scheduling problem which, in addition to the standard restriction involving pairs of elements that cannot be placed together, considers pairs of elements that must be placed to gether. A set S is a colored-independent set if, for each color class V_I, S∩V_I=V_I or S∩V_I=0. In particular,β_PRT(G), the independence partition number, is determined for all paths of order n. Finally, we show that the resulting decision problem for graphs is NP-complete even when the input graph is a path.