MO640 - Exercises - C1P, Setubal and Meidanis 1997

Exercises marked with (*) require further reading/search beyond the suggested texts.

2. Find a situation in the improved placement algorithm in which processing a new set in DFS creates all three types of classes: empty, full, and partial.

Answer:

Assume we have the following data structure generated by the improved placement algorithm:

structure before

This situation could be the result of processing sets:

S1 = { 3, 2 }
S2 = { 2, 5, 7 }

By processing the set S3 = {3,5}, the algorithm will:

color 3;
color the first class node (it's a full class);
do not color the second class node (it's an empty class);
color 5;
do not color the third class node (it's a partial class).

So we'll have the following structure to check for the C1P property:

structure after

where all three types of classes occur. Notice that the processing order S1, S2, S3 corresponds to a DFS order in the strict overlap graph.

MO640 Home