• Definition: Sequential Graph Partitioning - SGP

Sequential Graph Partitioning

An instance of the sequential graph partitioning (SGP) problem consists of a graph G=(V,A)  and a non-negative integer X  that is used as the limit for each partition fragment. There is a total ordering defined on the vertex set     such that   for i<j. A weight w(v)   is assigned to each vertex and a length l(v_i,v_j)   to each edge  . The goal is to partition V into subsets with each V_k  holding only consecutive vertices - thus the name sequential graph partitioning in contrast to traditional graph partitioning which is NP-complete [Hyafil and Rivest, 1973]. The optimality constraints are that partitioning

• minimises the sum of the lengths of the edges that start and end in different partition fragments and
• leaves the `weight' of each fragment V_k less than or equal to X.

In section 5.6.3, we will give an example of SGP, actually the instance of SGP that results from reducing the IP example of figures 5.2, 5.4 and 5.6 to an SGP problem.

Definition: Sequential Graph Partitioning - SGP

Instance:

• An undirected graph G=(V,A) with a total ordering defined on the vertex set
  such that for all i<j. is the set of edges.
  For convenience we assume an additional dummy vertex v₀ and that i<j for all .
• A function assigning a weight w(v) to each vertex ,
• a function assigning a length l(v_i,v_j) to each edge and
• a positive number X.

Question:

 
Is there a partition of V into subsets of consecutive vertices, i.e.

  imposed by a set P of partition vertices and which minimises  

(19)

such that  

(20)

for  ?
The sets   are defined as

for . A'  is the union of these