Difference between revisions of "TADM2E 5.20"
From Algorithm Wiki
(Undo revision 884 | Why are u doing this? What's the point? It's wiki for learning book) |
|||
| 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) | ||
Latest revision as of 08:13, 23 July 2020
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.--Bkarpov96 (talk) 08:53, 6 July 2020 (UTC)
