THE SHIFTING ALGORITHM TECHNIQUE FOR THE PARTITIONING OF TREES

In this paper we survey a design technique for partitioning on trees. This technique, the shifting algorithm technique, is a top-down greedy technique. A partition of a tree is represented by associating cuts w ith edges of the tree. The basic operation of the technique is a local transformation called a shift of a cut from an edge to an adjacent ed ge of the tree. We review several shifting algorithms for different op timization criteria for partitioning. In these algorithms, different s hifts and different greedy decisions are utilized. A mathematical fram ework created for validity proofs of shifting algorithms is introduced . Various applications are outlined.