Exercises marked with (*) require further reading/search beyond the suggested texts.
3. Find a situation in the improved placement algorithm in which processing a new set in DFS destroys the C1P by not having and empty neighbor to place an uncolored subclass.
Answer:
Consider the following sets:
S1 = { 2, 3 }
S2 = { 2, 5, 7 }
S3 = { 5, 6, 7 }
S4 = { 2, 5, 6 }
The order S1, S2, S3, S4 is a valid DFS order. The family has the C1P up to set S3. When set S4 is added, it destroys the C1P because class {5, 7} must be split but there is no empty neighbor to place uncolored sublcass {7} near to.
© 2015 Joao Meidanis