While solving the problems on Techgig.com, I got struck with one one of the problem. The problem is like this:
A company organizes two trips for their employees in a year. They want to know whether all the employees can be sent on the trip or not. The condition is like, no employee can go on both the trips. Also to determine which employee can go together the constraint is that the employees who have worked together in past won't be in the same group. Examples of the problems:
Suppose the work history is given as follows: {(1,2),(2,3),(3,4)}; then it is possible to accommodate all the four employees in two trips (one trip consisting of employees 1& 3 and other having employees 2 & 4). Neither of the two employees in the same trip have worked together in past.
Suppose the work history is given as {(1,2),(1,3),(2,3)} then there is no way possible to have two trips satisfying the company rule and accommodating all the employees.
Can anyone tell me how to proceed on this problem?