The argument around 6:00 that leads to the "without loss of generality" remark is quite handwavey and I didn't understand it. Besides that the whole video is very well explained
I don't really understand why the WLOG was necessary, but essentially, if you pick the vertex with degree one, then you remove that vertex and it's (singular) child. However, if you pick the other vertex (let's call it V), then you will be removing V, the vertex with degree one, AND all the other children of the vertex V. The first case always yields an MIS >= because the second case's vertices are a subset of the first case's vertices. Hope this helps.
Very good explanation, really helped me with my homework. Thanks.
Quality content, great job!
Thanks for your explanation. I implement the code based on your algorithm. it works
can you share your code for me? I really need it for my assignment.
Great explanation. Thanks
The argument around 6:00 that leads to the "without loss of generality" remark is quite handwavey and I didn't understand it. Besides that the whole video is very well explained
I don't really understand why the WLOG was necessary, but essentially, if you pick the vertex with degree one, then you remove that vertex and it's (singular) child. However, if you pick the other vertex (let's call it V), then you will be removing V, the vertex with degree one, AND all the other children of the vertex V. The first case always yields an MIS >= because the second case's vertices are a subset of the first case's vertices. Hope this helps.
In case of degree of a node being 0 or 1, shouldn't we have a case where the node is not included
No. He explained why at the start