0
$\begingroup$

Here's a problem that uses graph to find task assignment among a group of workers. Assume there are N number of tasks to be completed, with dependencies among the tasks. For example, task i depends on task j, which depends on k, etc. A directed graph can be used to model this, G = (V, E), where the Edge (a, b) implies that task b depends on task a.A task should be assigned to one worker, and a worker can be assigned multiple tasks. In the special case where the task dependencies form a cycle, e.g, task i depends on task j, which depends on task k, which depends on task i, the same worker should be assign the cycle of tasks.

Assume the goal is to assign all the tasks to the workers while minimizing the maximum number of task per worker (there is no limit on the number of workers). What is the most efficient way to assign the tasks? What is the max number of assigned tasks per worker?

$\endgroup$
2
  • 1
    $\begingroup$ Where did you encounter this task? What's the original source or motivation? We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing. $\endgroup$
    – D.W.
    Dec 21 '21 at 22:51
  • 1
    $\begingroup$ What approaches have you considered? What progress have you made? We're happy to help you understand the concepts but just solving exercise-like tasks for you is unlikely to achieve that. You might find this page helpful in improving your question. We're not looking for questions that consist solely of the text of an exercise-like task. $\endgroup$
    – D.W.
    Dec 21 '21 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.