MO640 - Exercises - PQR Trees, Meidanis, Porto, and Telles 1997

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

1. Find a suitable dividing set H for the collection C = {bdfg, cde, abf} under U = abcdefg.

Answer:

The strictly overlapping graph G(C) is:

strictly overlapping graph

As there is only one connected component in G(C), the union of component is abcdefg which is trivial, so we need to find a nontrivial twin class. Twin classes in a path after adding {b,d,f, g} , {c,d,e} , and {a,b,f}:

path with twin classes

So, both {b,f} and {e,c} are twin classes and therefore suitable to be H.


MO640 Home

© 2015 Joao Meidanis