TADM2E 5.15 - Revision history

Matt: Undo revision 809 by Hdyldhdlgzos (talk)

2020-07-23T15:58:04Z

Undo revision 809 by Hdyldhdlgzos (talk)

2020-07-16T06:28:37Z

Blanked the page

2017-01-01T01:36:39Z

2015-03-25T15:28:41Z

Created page with "This reduces to two-colour graph problem."

New page

This reduces to two-colour graph problem.

← Older revision	Revision as of 15:58, 23 July 2020
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.

← Older revision		Revision as of 06:28, 16 July 2020
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.~~

← Older revision		Revision as of 01:36, 1 January 2017
Line 1:		Line 1:
−	~~This~~ reduces to two-colour graph problem.	+	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.