graphclassificationpartitiondisjoint-sets

Minimal count of the disjoint set partitioning


I am looking for an efficient algorithm (if there is one) to solve the following problem: Given a set S, whose elements are sets with only two elements. For simplicity, let' s say "two elements" are integers from 1 on. As an example, S can be decribed like: S = {{1, 2}, {2, 3}}. We define R as a radix, which means the integers in the set can not be greater than or equal to R, a bit different from integer 10 in the decimalism. We now define a group G which is merged by the disjoint sets in S with the total count of integers in G less than or equal to R. For example, S = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}, R = 4, and then G1 = {{1, 2}, {3, 4}}, G2 = {{1, 3}, {2, 4}}, G3 = {{1, 4}, {2, 3}}. Therefore, in this example, the minimal count of groups is 3.

I want to know if there is any algorithms can efficiently solve this problem with minimal groups. Before posting this problem, I was thinking to transform it into a graph clustering problems, however I find it hard to do with it. I hope I can get some help here, thank you!


Solution

  • I think I must have misunderstood this question, it seems so trivial.

    Let

    then

    M = ( 2 * N ) / R, rounded UP to the nearest whole integer
    

    The rounding up is needed because if 2 * N is not divisible by R, then there will one G group with less than R elements.

    e.g for your example: M = 2 * 6 / 4 = 3