9.11. Summary of Relational Properties 357
...
...
t - 1^n - (t - 1)What is the minimum time schedule forDn;t? Explain why it is unique. How many
processors does it require?
(c)Write a simple formula,M.n;t;p/, for the minimum time of ap-processor
schedule to completeDn;t.
(d)Show thateverypartial order withnvertices and maximum chain size,t, has
ap-processor schedule that runs in timeM.n;t;p/.
Hint:Use induction ont.
Problems for Section 9.6
Practice Problems
Problem 9.21.
In this DAG (Figure 9.13) for the divisibility relation onf1;:::;12g, there is an
upward path fromatobiffajb. If 24 was added as a vertex, what is the mini-
mum number of edges that must be added to the DAG to represent divisibility on
f1;:::;12;24g? What are those edges?
Problem 9.22. (a)Why is every strict partial order a DAG?
(b)Give an example of a DAG that is not a strict partial order.