Sorry for my English.
Here is the question: $G=(v,e)$, undirected graph, $V=\{v_1,v_2,\ldots,v_n\}$. the vertices are organized in sequence from the smaller one to the biggest $v_1,\ldots,v_n$. We will define a spread distribution $(C_1,\ldots,C_k)$ as follows:
- For each $i,j$, $C_i \cap C_j = \emptyset$.
- $\bigcup_{i=1}^k C_i = V$.
- Every $C_i$ consists of consecutive vertices, i.e. $v_{j+1},\ldots,v_{j+d}$.
- The vertices in $C_i$ form an independent set.
I need to find a Greedy Algorithm for this problem in $O(|V|+|E|)$.
I tried many ways, but the main problem for me is to handle the situation where $(v_3,v_4) \notin E$ and $(v_4,v_1) \in E$ (I check in my algorithm only "neighboring" vertices, $v_1-v_2,v_2-v_3,\ldots,v_{n-1}-v_n$).
Any ideas? Thank you!