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

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

2. Find a suitable dividing set H for the collection C = {he, dc, fb, dcifbg, ae, gb, ic, jc} under U = abcdefghij.

Answer:

The strictly overlapping graph for the collection is:

So, three possible H sets are the unions of components:

H = aeh
H = bfg
H = dcifbgj