May 1st, 2013, 09:49 AM
Disjoint pairs problem
Hi to all,
excuse me in advance if I have done something wrong in posting this thread (I'm new ).
My problem is the following:
I have a set of pairs identified by two end point: u and, that respectively represent two process connected (u sends and v receives), and each process can hold one connection at a time, so I have to divide the computation in communication rounds so that in each round communicate as many process as possibile. This example may explain better the idea:
If I choose 1-2 in a communication round I can't choose in the same communication round 1-3, 1-4, 2-1, 2-3, 4-2 because these pairs involve process 1 or 2.
I tried to solve the problem with a greedy algorithm that for each pair choose a round that doesn't intersect with it and if there are no feasible rounds it creates a new one.
I find lots of problems in literature regarding path coloring, arc coloring and interval scheduling, but I'm not sure if I'm dealing with a difficoult problem, I mean NP-hard, or with a polynomial one, so I can't prove if my solution is optimal. Can you help me? Do you think my problem is reconducible to path coloring? If so, are there some approximation algorithms that give less than O(n^2)?
Thanks in advance to all
Tags for this Thread
Click Here to Expand Forum to Full Width