<p>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?</p>

CC BY-SA 3.0
2011-08-04T14:57:46.373Z
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.
Kaveh
CC BY-SA 3.0
2011-08-04T17:07:40.257Z
I agree with Kaveh.  How would it be any easier than doing the work for $|C|$ graphs on the same number of vertices?
Andrew D. King
<graph-algorithms><ds.data-structures>
Connected Components over Graph with "colored" edges.
Giuseppe
# Connected Components over Graph with "colored" edges.

(Asked by: username_0 on 2011-08-04)

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?

**Tags:** graph-algorithms, ds.data-structures

> **Comments:**
> **username_1**: 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.  
> **username_2**: I agree with username_1.  How would it be any easier than doing the work for $|C|$ graphs on the same number of vertices?  

---

## 0 answers

