I face a problem that is related to (strongly) connected components. Let $G=(V,E)$ be an undirected graph.
I want to find subgraphs $G_1,G_2, \dots,G_n$ of $G$ such that
- they do not overlap (i.e. don't share any nodes)
- each two nodes in a subgraph are connected by an edge, i.e. $\forall i \forall n,m\in V_i$ then $\{m,n\}\in E_i$ where $G_i=(V_i,E_i)$.
My question is: How to solve this problem? Is there any specific name of this problem?
Edit: The graph I am dealing with is very sparse. Coloring based approximations may not work as the complement graph would be huge (not able to store it in memory).