1090181
| Frage | Antworten |
| Give a dynamic programming algorithm that takes an n-node path G with weights and returns the total weight of the independent set of maximum total weight. The running time should be polynomial in n, independent of the values of the weights. | solution is here: www.sussex.ac.uk/Users/davidw/courses/pa/resources/exercises/answers/sheet9answers.pdf Note that G is a path not a graph ! The solution is also applicable for a tree . Was this question exactly in the previous comprehensive exam T132 ? |
Möchten Sie mit GoConqr kostenlos Ihre eigenen Karteikarten erstellen? Mehr erfahren.