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
    Is $k$ given to you ahead of time or are you trying to minimize it?2011-03-10
  • 0
    Im trying to minimize it (by Greedy algorithhm). Thank u2011-03-10
  • 1
    Try precomputing for each vertex $v_i$ the minimal $j > i$ such that $(v_i,v_j) \in E$ (if any).2011-03-10
  • 0
    I got it. Thank u very much. You help me a lot.2011-03-11

0 Answers 0