http://en.wikipedia.org/wiki/Graph_partition
On Nov 4, 2:23 pm, khaled <[email protected]> wrote: > 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.
