0
$\begingroup$

I am trying to solve a graph theory problem. I have an undirected graph where the nodes have node weights n and edges have edge weights g. I want to be able to select the subgraph such that the total weight of nodes+edges is maximized. Each node doesn’t count equally though, as each node has a nonuniform weight w.

I think this is also equivalent to the 0/1 knapsack problem except that there are additional benefits to each pair of items put into the knapsack, in addition to their singular benefit.

What is the name of such a graph theory problem?

$\endgroup$
  • $\begingroup$ Are the edge/node-weights non-negative? What kind of constraints do you have on the subgraphs? Is it allowed to choose any subgraph? If all weights are non-negative, then your problem is trivial because the graph itself is the optimal-value... $\endgroup$ – Tobias Windisch Apr 22 '16 at 15:14
0
$\begingroup$

https://www.or-exchange.org/questions/13555/maximal-subset-include-nonuniform-node-weights-and-node-values

I cross-posted: it's equivalent to the quadratic knapsack problem. I think that formally it's the maximal weighted clique problem, with weights on both nodes and edges.

$\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.