University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

CSC 477/677 Assignment 6

Due date: Tuesday, April 1, 2008, 4:00 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me on or before the due date.
  1. Walk through the steps of Kruskal's algorithm, when it is used to find a minimum spanning tree of this graph.. If you work the algorithm correctly on this graph, there will definitely be at least one step where path compression is used. Describe this step in detail. (If there is more than one step where path compression is used, you only have to describe one of them in detail.)
    Here is an eps version of the same graph.
  2. Work Exercise 23.2-6 page 574 of your textbook.
  3. A limited degree spanning tree is a spanning tree whose degree is bounded by a given constant. For example, the minimum spanning tree of this graph has weight 4, but the minimum degree 3 spanning tree of that graph has weight 8.
    Can you construct an efficient algorithm for computing a limited degree spanning tree for a weighted graph?
    If not, can you construct any algorithm for computing a limited degree spanning tree for a weighted graph?
  4. Suppose G is a graph where vertices are partitioned into layers L1, L2, . . . , Ln such that any two adjacent vertices are in the same or adjacent layers.
    Design an algorithm which determines whether such a graph is connected, using the Union/Find method. No layer has more than m vertices, and the amount of memory your program can use is O(m). However, n, the number of layers, can be very large. The program is allowed to look at two layers at a time, in order, and cannot backtrack. That is, the program can look at L1 and L2 simultaneously, observing all the edges between those vertices. It then moves on, looking at L2 and L3 simultaneously, but it can never look at L1 again, and so forth.
    Here is an example where m = 6. This graph is connected; but how can your program determine that? Think of m as small, and n as very large.
    This kind of graph is similar to a layered graph, but is not exactly the same.

Back to Course Page