I am working on a problem which could be reduced to a graph optimization problem as below.
A set of colored nodes is given.
The edges are to be inserted between the nodes.
A node can have only 4 edges at max.
A table provides rules for profit contribution from the edges.
An edge connecting red to red: profit is 10
An edge connecting red to blue: profit is 20
The total number of colors is typically around 20 to 30, but it can go as high as 50. Correspondingly the table for profit(edge) would be a long list but it won't list all possible combinations. The profit for edges not specified in the table is assumed zero.
The problem is to optimize the connections (edges) such that the total profit is maximized.
I am wondering if this problem, maybe in some other way, is known. If so, please provide any pointers that might be of help. Thanks.