The problem is to find an algorithm that colors all the edges in any arbitrary tree T with a root r, let's say in blue and red, such that the number of blue edges is maximal and there isn't more than three blue edges in a row on any path starting at r.Update:I've tried a top-down solution, but I'm not able to figure out how to build the recursion using the condition of maximum three consecutive edges.Maybe the bottom-up approach will be better. There I'd start colouring all edges with blue and write down the longest color sequence present on any path to the leaves. Then, if the sequence length is equal three, I have no other option than coloring the edge in red.I'm not sure if this is always leading to the optimal result, cause it looks more greedy than dynamical.The question is, how to get the optimal result? And how to be sure it's correct?
Edge coloring optimization using dynamic programming
algorithms;optimization;trees;dynamic programming;colorings