http://www.justputt.com/deg-graph/
 |
| Powered by phpBay Pro |
Find an induced subgraph H, of a undirected graph G of maximum size such that all verticies of H have deg > k
Input:
- Undirected Graph G = (V, E)
- Integer k
Goal:
- Find an induced subgraph of H = (U, F) of G of maximum size
- Maximum size (maximum in terms of the number of verticies) such that all verticies of H have degree at least k.
I need to design a program but am finding it hard to understand my problem. Could someone explain a unduced graph; or possibly intuitivley explain an algorithm which would solve my problem.
If a vertex has degree less than k it can't possibly be part of the solution.
So throw out all verticies with degree less than k.
Now in the resulting graph, any vertex with degree less than k cannot be part of the solution.
So iterate: keep throwing out vertices with degree less than k until you are left with an induced subgraph all the vertices of which have degree at least k.
By construction, there cannot be a larger solution.
Dan
|
 Left Handed Tour Edge Bazooka Super Lite 18 Deg Titanium 5 Wood Firm Flex Graph  US $14.99
|
| Powered by phpBay Pro |
