Example

   We want to see how SGP-opt works for the graph of figure 5.9 and X=10. Figure 5.11 shows the matrix for the values of . This matrix can be pre-computed in O(n²) steps. It shows the loads of all possible fragments. Because of X=10 we can discard all fragments with a load greater than X, e.g. a fragment is not possible because . For graphs resulting from an IP instance, the matrix shows if there exists a partition that satisfies the constraint at all: the diagonal shows the loads for the fragments consisting only of one vertex (i.e. one time point). If there was a load greater than X in the diagonal then this would mean that there would be a timepoint that would be included in more than X intervals. Therefore this point could never be part of any partition range because it would cause the corresponding fragment to exceed the maximum load X. Thus there would be no partition that satisfied the maximum load constraint. The matrix shows that such situations arise for X<9.

Table 5.2 shows the values calculated by SGP-opt. It is similar to table 5.1. It is longer because the graph of figure 5.9 contains not only the endpoints E(R) but also the startpoints S(R). Nevertheless, it delivers the same result as in section 5.5.2.