I am a biologist doing some computational work. I encountered a problem and need some help since I don’t have much algorithmic background.
Assume we have a non-directed, weighted graph, in which every node has some categorical attribute, e.g. color. I want to break the graph into sub-graphs in which there is at most one node of each color. Decisions should be made by trying to preserve the strongest connections (edges with highest weights). For example, let’s look at the graph below (I didn’t include weights as this would be hard to see):
In this case, I would like to break the graph into two sub-graphs (assuming that this is what the weights indicate):
Two notes (I don’t know if they matter though):
- The maximal number of colors is known in advance
- After the graph was broken, I don’t really care about the topology anymore – I just want to know which nodes ended up together.
My first question is: does this look familiar to you? Has this problem been solved before? Maybe it’s a variant of something every CS student learns? If so, can you please refer me to relevant information/literature?
If not, Then I’d like some help on how to approach this. Can you give some ideas on how to start developing and algorithm that can solve this type of problem?
Any other advice would be useful. Thank you!