UNLV Computer Science 677: Design and Analysis of Algorithms

Spring 2001

Graduate Homework Assignment 1.

Due April 2, 2001

You may discuss this assignment with other students in the class, or other persons. But you must actually write the assignment in your own hand. You must turn in the homework on letter-sized paper, with your name at the top of each page. Use pen or pencil, any color.

In the narrative portions of the problems, please write legibly.

Do not write your homework as a computer file and turn in a printout.
Let G be a directed graph with n nodes and m edges.
The transitive closure of G is defined in your textbook, and an algorithm for finding the transitive closure is given. However, it appears that transitive reduction is not discussed in the textbook. You will have to research the definition.

1. Find an efficient algorithm for computing the transitive reduction of G.
2. Suppose that G is acyclic. Do exactly one of the following:
   1. Find an efficient algorithm for computing the transitive reduction of G which is better than the algorithm you gave for the above problem.
   2. Argue that it does not help to use the fact that G is acyclic, that is, the best algorithm for finding the transitive reduction of a directed acyclic graph does not utilize the fact that it is acyclic. (It is not necessary to give a formal proof, just informal reasons for believing it.)
3. Come up with an application. That is, think of some problem, that might arise in a real-life application, for which it might be helpful to be able to compute transitive reduction of a directed graph. Explain your problem and how you could apply transitive reduction, in narrative form, not more than one page.