3
$\begingroup$

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:

  1. For each $i,j$, $C_i \cap C_j = \emptyset$.
  2. $\bigcup_{i=1}^k C_i = V$.
  3. Every $C_i$ consists of consecutive vertices, i.e. $v_{j+1},\ldots,v_{j+d}$.
  4. 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!

  • 0
    I got it. Thank u very much. You help me a lot.2019-04-08

0 Answers 0