• Algorithm SGP-opt

Optimal Solution for SGP

   In this section, we present an algorithm that gives an optimal solution for SGP and - because of the reduction M presented in the previous section - also to IP. The only change to Kernighan's algorithm has to reflect the slightly different calculation of a fragment's weight.

The approach taken by the algorithm SGP-opt  is similar to the one taken for IP-opt. It is based on dynamic programming: the graph is scanned, beginning with v₁ and proceeding one vertex in each step. In step i, i.e. having reached vertex v_i, the algorithm knows an optimal partition for each of the subgraphs containing respectively. It then seeks the vertex v_j prior to v_i that minimises the partial costs c(v_i) for if the graph ended at v_i and the previous breakpoint had been v_j. The minimising v_j is stored as  . Finally, when reaching v_n, the optimal partition for the entire graph can be found in .

The following data structures and functions are used by the algorithm in addition to the ones already introduced in the context of SGP:

• For convenience, the algorithm assumes a dummy vertex v₀ with w(v₀)=0.
• The sum of edge lengths that are cut by a partition vertex v_k are stored in  
  for . Please note that
  and that

• The weight of a vertex fragment is stored in

  for , i.e. the sum of weights of vertices plus the sum of lengths of edges starting at or before v_x and ending in some vertex .

• c(v_i)= minimal partial costs for a partition up to vertex v_i.
• number of vertex preceding v_i that leads to (minimal) partition costs c(v_i).

The algorithm is shown in figure 5.10. It adopts a similar structure to the one used for IP-opt in figure 5.5. This is intended to emphasise the similarities between IP and SGP. For a proof of correctness the reader might refer to [Kernighan, 1971].

Algorithm SGP-opt

• c(v₀) = 0
• for i=1 to n do
  • if then
    output ``No optimal partition.'' ; stop.
  • 
    Let for the minimising v_j.
    If there is more than one qualifying v_j then choose the smallest.
• [] /* output of breakpoints in descending order */
• p=v_n
• while do
  • output p

The algorithm SGP-opt for computing an optimal partition for an instance of SGP.