I have the following graph problem. I would appreciate if some graph theory expert points me to what is the scientific name under which it is known in graph theory.
Given a directed graph G=(V,E,W) where W is the weights of the edges. I would like to divide the graph into subgraphs G_i=(V_i, E_i, W_i) such that: 1) Each subgraph is of size at least 2 and <= N and where N is a given parameter strictly less than |V|. For large graphs actually N << |V|. In other word 1 < |V_i| <= N. 2) The sum of the costs of the edges of the subgraphs is maximized. I.e. the division into subgraphs is such that the total sum of the cost of edges in the subgraphs is maximized (excluding of course the edges in the original graph that are no longer in any of the subgraphs). Any ideas? Thanks, Khaled -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
