Studiando per i miei algoritmi, testando gli esercizi di Algorithm Design Manual, ma sono bloccato su questo. So che devo mantenere il punteggio in qualche modo.
Let
G = (V,E)be a tree with arbitrary weights associated with the vertices.Give an efficient algorithm to find a minimum-weight vertix cover of
G.
Alcuni dei miei pensieri:
- I genitori della foglia (chiamiamola p) dovrebbero essere scelti perché di solito sono più efficienti. Quindi contrassegnare tutti i parenti per essere "coperti". Quindi ti rimane un albero più piccolo. Ma ci sono contro esempi, dal momento che è ponderata. Questo è vero solo per i grafici non pesati.
Inoltre, sono confuso circa la parte 3. di questa soluzione fornita da Skiena. Qualcuno potrebbe spiegarmi questo? E anche parte 4., cosa significa "backtracking" significa punteggio?
