0
$\begingroup$

Let G be a undirected graph with weighted edges. I want to find a connected subgraph which has at most L nodes(vertices) whose sum of edges is maximum. It sounds similar to MWCS or PCST but here only the edges are weighted and there is a limit on no of nodes in the subgraph. These are related papers I found for solving MWCS or PCST: http://dimacs11.cs.princeton.edu/workshop/ElKebirKlau.pdf http://dimacs11.cs.princeton.edu/workshop/AlthausBlumenstock.pdf

PS: All weights are positive unlike in MWCS.

$\endgroup$
1
$\begingroup$

You might want take a look at our paper that considers what we call a generalized MWCS problem (https://arxiv.org/abs/1605.02168) and corresponding solver (https://github.com/ctlab/gmwcs-solver/). There, unlike in classical MWCS, edge weights (both postitve and negative) are allowed. It works pretty well for the practical instances that we have.

$\endgroup$
  • 1
    $\begingroup$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. $\endgroup$ – Glorfindel Apr 18 '17 at 8:36
0
$\begingroup$

We can do this using linear programming. Let your objective function be

x1 e1 + x2 e2 + ..... xn en

where xk is a boolean variable to show whether to select kth edge. And ek is the edge weight. Here, n is the no of edges. Then we can formulate the following constraints:

x1 + x2 + ... xn <= p, where p is the no of edges we want.

If one edge k, is guaranteed to be in the subgraph to be selected, then formulate constraints outwards from that edge. For example, if u and v are edges connected to k, then the constraints u<=k and v<=k will be present. And so on for all the edges. This will ensure connectedness of the selected graph. Feeding this to any linear programming solver like lp_solve will give boolean values of all xs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.