TADM2E 5.20 - Revision history

Bkarpov96: Undo revision 884 | Why are u doing this? What's the point? It's wiki for learning book

2020-07-23T08:13:59Z

Undo revision 884 | Why are u doing this? What's the point? It's wiki for learning book

Fucs: Undo revision 869 by Bkarpov96 (talk)

2020-07-22T22:53:49Z

Undo revision 869 by Bkarpov96 (talk)

Bkarpov96: Undo revision 858 by Bkarpov96Wars (talk)

2020-07-22T11:21:39Z

Undo revision 858 by Bkarpov96Wars (talk)

Bkarpov96Wars: Blanked the page

2020-07-22T00:22:26Z

Blanked the page

Bkarpov96: 5.20 solution

2020-07-06T08:53:31Z

5.20 solution

New page

<pre>
Traversing the graph G DFS O(n + m)
- If vertex M has degree >= k, add it to U
- - If vertex J (parent of M) was added to U, then add an edge MJ to R
- Continue DFS for children of vertex M with the pointer on M and a flag indicating whether M was added to U

Since the condition requires finding the maximum induced subgraph, all matching vertexes and edges are added during the DFS.
If U and R do not contain elements at the end of the DFS, then the induced subgraph does not exist.
</pre>--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 08:53, 6 July 2020 (UTC)

← Older revision		Revision as of 22:53, 22 July 2020
Line 1:		Line 1:
−	~~<pre>~~
−	~~Traversing the graph G DFS O(n + m)~~
−	~~- If vertex M has degree >= k, add it to U~~
−	~~- - If vertex J (parent of M) was added to U, then add an edge MJ to R~~
−	~~- Continue DFS for children of vertex M with the pointer on M and a flag indicating whether M was added to U~~

−	~~Since the condition requires finding the maximum induced subgraph, all matching vertexes and edges are added during the DFS.~~
−	~~If U and R do not contain elements at the end of the DFS, then the induced subgraph does not exist.~~
−	~~</pre>--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 08:53, 6 July 2020 (UTC)~~

← Older revision		Revision as of 00:22, 22 July 2020
Line 1:		Line 1:
−	~~<pre>~~
−	~~Traversing the graph G DFS O(n + m)~~
−	~~- If vertex M has degree >= k, add it to U~~
−	~~- - If vertex J (parent of M) was added to U, then add an edge MJ to R~~
−	~~- Continue DFS for children of vertex M with the pointer on M and a flag indicating whether M was added to U~~

−	~~Since the condition requires finding the maximum induced subgraph, all matching vertexes and edges are added during the DFS.~~
−	~~If U and R do not contain elements at the end of the DFS, then the induced subgraph does not exist.~~
−	~~</pre>--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 08:53, 6 July 2020 (UTC)~~

← Older revision	Revision as of 08:13, 23 July 2020
Line 1:	Line 1:
	+	<pre>
	+	Traversing the graph G DFS O(n + m)
	+	- If vertex M has degree >= k, add it to U
	+	- - If vertex J (parent of M) was added to U, then add an edge MJ to R
	+	- Continue DFS for children of vertex M with the pointer on M and a flag indicating whether M was added to U

	+	Since the condition requires finding the maximum induced subgraph, all matching vertexes and edges are added during the DFS.
	+	If U and R do not contain elements at the end of the DFS, then the induced subgraph does not exist.
	+	</pre>--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 08:53, 6 July 2020 (UTC)

← Older revision	Revision as of 11:21, 22 July 2020
Line 1:	Line 1:
	+	<pre>
	+	Traversing the graph G DFS O(n + m)
	+	- If vertex M has degree >= k, add it to U
	+	- - If vertex J (parent of M) was added to U, then add an edge MJ to R
	+	- Continue DFS for children of vertex M with the pointer on M and a flag indicating whether M was added to U

	+	Since the condition requires finding the maximum induced subgraph, all matching vertexes and edges are added during the DFS.
	+	If U and R do not contain elements at the end of the DFS, then the induced subgraph does not exist.
	+	</pre>--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 08:53, 6 July 2020 (UTC)