title: Maximize number of subgraphs with a given minimum weight
body: <p>I have an undirected planar graph where each node has a weight. I want to split the graph into as many connected disjoint subgraphs as possible (EDIT: or to reach a minimum mean weight of the subgraphs possible), given the condition that each subgraph has to reach a fixed minimum weight (which is a sum of weights of its nodes). A subgraph containing only a single node is OK as well (if the node's weight is larger than the fixed minimum).</p>
  
  <p>What I have found out so far is a heuristic:</p>
  
  <pre><code>create a subgraph out of every node
  while there is an underweight subgraph:
    select the subgraph S with the lowest weight
    find a subgraph N that has the lowest weight among the neighbouring subgraphs of S
    merge S to N
  </code></pre>
  
  <p>Clearly this is not optimal. Has anyone got a better solution? (Maybe I'm just ignorant and this is not a complex issue, but I have never studied graph theory...)</p>
  
  <p>EDIT (more background details): The nodes in this graph are low-scale administrative units for which statistical data are to be provided. However, the units need to have a certain minimum population size to avoid conflicts with personal data legislation. My objective is to create aggregates so that as little information as possible is lost on the way. The neighbourhood relationships serve as graph edges, as the resulting units must be contiguous.</p>
  
  <p>Most of the units (nodes) in the set are well above the minimum threshold. About 5-10 % of them is below the threshold with varying sizes, as seen on the example (minimum size 50):</p>
  
  <p><img src="https://i.stack.imgur.com/0wXod.png" alt="Example situation"></p>