Timeline for Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 9, 2017 at 1:40 | comment | added | Laschet Jain | @miguel.martin If the Vertex Cover just contains vertices numbered 2 and 5, the edge between node 3 and 4 won't be covered. | |
| May 3, 2016 at 3:32 | comment | added | miguel.martin | I don't think the logic for the 2nd step is correct. If you consider a degenerate tree with 6 nodes going down all the way right (label them 1-6 corresponding to their depth). Then the first step of your algorithm will pick node 5. The second step will then possibly pick the first node (root) and then the second node (child) OR the third node. However, this is incorrect since you only want to pick node 2 and node 5 for a correct solution. | |
| May 21, 2013 at 18:43 | answer | added | A.Schulz | timeline score: 11 | |
| May 21, 2013 at 16:09 | history | edited | A.Schulz | CC BY-SA 3.0 | copy editing |
| May 21, 2013 at 4:58 | history | tweeted | twitter.com/#!/StackCompSci/status/336707461320957952 | ||
| May 21, 2013 at 4:50 | answer | added | Yuval Filmus | timeline score: 5 | |
| May 21, 2013 at 3:52 | history | asked | e_noether | CC BY-SA 3.0 |