Difference between revisions of "TADM2E 5.15"
From Algorithm Wiki
(Created page with "This reduces to two-colour graph problem.") |
(Undo revision 809 by Hdyldhdlgzos (talk)) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | + | To build a vertex cover, we need to keep '''at least''' one vertex for each edge. The independent set requires '''at most''' one vertex for each edge. | |
| + | |||
| + | Together it means we need to keep only '''exactly''' one vertex for each edge, this reduces to two-colour graph problem. | ||
Latest revision as of 15:58, 23 July 2020
To build a vertex cover, we need to keep at least one vertex for each edge. The independent set requires at most one vertex for each edge.
Together it means we need to keep only exactly one vertex for each edge, this reduces to two-colour graph problem.
