We have an undirected graph $G(V,E)$. Each edge $e \in E$ is associated with a set $C_{e}\neq \emptyset$ of colors, $C_{e} \subseteq C$. The problem is to find all the colored connected components. For example if we have $C=\{\;\mathrm{red},\;\mathrm{black},\;\mathrm{yellow}\}$. The Red connected components are all the connected components considering only the edges that contains red in the color set. Now a naive algorithm is to do the normal search for each $c\in C$. The cost seems to be $O(|C|(|V|+|E|))$. The question is: is it possible to do better?

  • 2
    $\begingroup$ I don't think it can be done faster than solving $|C|$ connected component problems (direct sum), but I don't know if what you described is the best way to do it. $\endgroup$ – Kaveh Aug 4 '11 at 14:57
  • $\begingroup$ I agree with Kaveh. How would it be any easier than doing the work for $|C|$ graphs on the same number of vertices? $\endgroup$ – Andrew D. King Aug 4 '11 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.