|
|
| 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)
| |
