Results 1 to 2 of 2

Math Help - Can I find the subsets of a domain given two sets

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    1

    Can I find the subsets of a domain given two sets

    Hi,
    I've two sets, X and Y. Sample data is in this shared PDF:
    https://docs.google.com/fileview?id=...MTYxMjU4&hl=en
    I want to divide the set X (or Y) so that I can get Set X1(A,B) and Set X2(C,D). Is it possible to do this mathematically (If yes, I'll try to code in Software which is my ultimate goal).
    I may want to divide it 'n' times (instead of 2, as in example) so that I can deal with manageable data.

    For those who are interested, I'll be applying Hungarian Matching algorithm on the divided sets. As of now, the data is huge and even optimal implementations take huge amount of memory (which we don't have).

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by rajetta View Post
    Hi,
    I've two sets, X and Y. Sample data is in this shared PDF:
    https://docs.google.com/fileview?id=...MTYxMjU4&hl=en
    I want to divide the set X (or Y) so that I can get Set X1(A,B) and Set X2(C,D). Is it possible to do this mathematically (If yes, I'll try to code in Software which is my ultimate goal).
    I may want to divide it 'n' times (instead of 2, as in example) so that I can deal with manageable data.

    For those who are interested, I'll be applying Hungarian Matching algorithm on the divided sets. As of now, the data is huge and even optimal implementations take huge amount of memory (which we don't have).

    Thanks
    From what I understand, you have a weighted bipartite graph and you want to divide it into smaller subgraphs, as part of an overall divide-and-conquer strategy.

    This is only possible if the data looks like your diagram, where there are no edges between {A,B} and {5,6,7,8} or between {C,D} and {1,2,3,4}. For a general bipartite graph this may not be the case.

    I don't know if there's a commonly used term, but let's say you're looking for "isolatable" sub-graphs.

    A naive algorithm comes to mind, which would be very slow for large graphs. Check a given pair in set X, say S1 = {A, B}. Consider the set S2 of all vertices in Y connected by edges to {A, B}. If S2 = Y, move on to another pair. Otherwise we know S2 is a proper subset of Y. Now check the set S3 = X - S1 and start building up a set S4 of all vertices in Y connected by edges to S3. If you find any element of S4 belonging to S2, move on to another pair. Otherwise, if you find that S2 intersect S4 is the empty set, then you've found your isolatable subgraph. Iterate all 2-subsets of X, then all 3-subsets of X, etc. If you start from 2-subsets and work upwards, you will not need to recursively look for subgraphs in your subgraphs, because they will already be as small as possible. You can stop checking k-subsets when k exceeds half the order of X.

    In practice you'd want to be using boolean arrays, rather than building up new lists and using some sort of contains() function.

    Depending on your needs, this naive method might be good enough?

    I've never worked on an assignment problem algorithm before, so I'm not sure what other approaches you might consider besides your proposed divide-and-conquer.

    (Made some small edits.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving 2 sets are subsets of each other
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 19th 2010, 10:31 AM
  2. Subsets of Non-Measurable sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 14th 2010, 10:03 AM
  3. Sets and subsets
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 1st 2009, 11:33 AM
  4. Sets & Subsets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 21st 2009, 03:57 PM
  5. subsets/open sets
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 12th 2007, 09:27 AM

Search Tags


/mathhelpforum @mathhelpforum