Optimal Deterministic Algorithm for the Hammock(2,2)-Poset Cover Problem. - Ordanel, Ivy D.
Consider the ordering of different tasks in Figure 1. Suppose a teacher gives those tasks to students and the students need to finish all of them. From the graph, there are some tasks that are dependent on other tasks. For example, Tasks 2, 3, and 4 need to be accomplished first before proceeding on Task 5. There are also some tasks that do not have dependencies. For example, Task 6 is not dependent on Task 7, so it does not matter which one between them will be started first. With this ordering, one student can do all the tasks in the following order: Task 1 →Task 2 → Task 3 → Task 4 → Task 5 → Task 6 → Task 7 → Task 8. Another student can accomplish all the task as follows: Task 1→ Task 3 → Task 2 → Task 4 → Task 5 → Task 7 → Task 6 → Task 8. There are actually 12 possible ways on which a student can finish all the tasks. This is a typical scenario ? an ordering is given and the flow of events . . .