In a connected / undirected / node weighted (with both positive and negative weights) network, there are many papers studied about the 'Maximum weight connected subgraph' problem. But are there any algorithms (even heuristic) to find highly weighted (not necessarily maximum) subnetworks that are densely inter-connected?

  • 2
    $\begingroup$ You'll need to better define "highly weighted" and "densely inter-connected" to get meaningful answers. $\endgroup$ – R B Feb 23 '15 at 12:15
  • $\begingroup$ In a connected, undirected, node-weighted network with non-negative weights one can just take the whole graph. Are you allowing negative weights? Further, is a bounded degree subgraph sufficiently interconnected, or is something like c-connectivity for small c enough? $\endgroup$ – András Salamon Feb 23 '15 at 16:44

Your Answer

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

Browse other questions tagged or ask your own question.