Difference between revisions of "TADM2E 5.20"
From Algorithm Wiki
(5.20 solution) |
(Undo revision 884 | Why are u doing this? What's the point? It's wiki for learning book) |
| (3 intermediate revisions by 3 users not shown) | |
(No difference)
| |
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)
