1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Greedy can be correct, and dynamic programming can not solve every problem. Have you tried proving your algorithm correct? $\endgroup$ – Raphael Apr 14 '17 at 11:51
  • $\begingroup$ What is your question, anyway? $\endgroup$ – Raphael Apr 14 '17 at 11:52
  • $\begingroup$ I've updated the question. $\endgroup$ – xbilek18 Apr 14 '17 at 17:07
  • $\begingroup$ Please try the techniques suggested in the resources at cs.stackexchange.com/tags/dynamic-programming/info. Can you write a (possibly slow) recursive algorithm that is guaranteed to generate the optimal solution? $\endgroup$ – D.W. Apr 14 '17 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.