pseudocode:
void recursive('k'){ // 'k' and 'i' vertices sumA = 0; sumB = 0; for each non visited 'i' neighbor do{ recursive('i'); sumA = sumA + b['i']; sumB = sumB + max(a['i'], b['i']); } a['k'] = 1 + sumA; b['k'] = sumB; } void main(){ a = b = 0; //initialize tables with 0 (zeros) recursive('X'); //let 'X' be an arbitrary root cout<
need proof that max(a['X'], b['X'])
is the cardinal of the maximum independent set in the tree. What am I missing ?
Thank you in advance.