'Finding isomorph sub-graph with minimum (edge) weight

I have an undirected graph G with edge weights and want to find a sub-graph that is isomorph to some other given graph H, such that the sum of all edge weights in the sub-graph is minimal. H is undirected as well but doesn't have any edge weights.

  • Is there an algorithm to find the minimal sub-graph?
  • If G is a fully connected graph, does that simplify the problem?
  • Follow-up: what if H also has edge weights and the goal is to minimize the sum of f(wH, wG) for some function f of the weights of an edge in H and its corresponding edge in the sub-graph of G
algorithmgraphcomputer-sciencesubgraphisomorphism


Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source

Related Questions