Timeline for Greedy algorithm for vertex cover
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 14, 2021 at 22:07 | vote | accept | Mario Giambarioli | ||
| Aug 6, 2020 at 20:12 | comment | added | Yuval Filmus | It will choose, say $A$, and add its three neighbors $B,C,D$. This is actually optimal – you need three vertices to cover all edges of the clique. | |
| Aug 6, 2020 at 16:19 | comment | added | Bernardo Subercaseaux | Why would the algorithm "add $3$ more vertices"? I see that it will add only $2$. The isolated vertex is not taken into account by the algorithm as step 1 only considers vertices with degree at least 1. | |
| Aug 6, 2020 at 15:56 | history | answered | Yuval Filmus | CC BY-SA 4.0 |