I'm searching for an algorithm that can calculate a suboptimal solution for:
color a graph with 3 colors some vertices already have a color and can't be changed the edges have values and the algorithm has to search for a solution where the sum of all the values of all the edges with vertices with the same color is smallest
this is for a practical problem: a wireless network with wireless accesspoints (vertices) you can ask the accespoints what neighbors they see and with what signal strength and i can create a graph out of that information some accespoints are not part of the network, and already have a channel assigned
and accespoint can only have 3 channels that don't interfere (1,6,11) these are the 3 colors
does anyone know a good algorithm that is powerful enough to solve this?
i heard this was used somewhere in cpu theory, where registers are already filled in (colored) and you need to assign registers to some programs (colors) but i can't find it