Shifting algorithms for tree partitioning with general weighting functions

Recently two shifting algorithms were designed for two optimum tree partitioning problems: The problem of max-min q-partition 4] and the problem of min-max q-partition 1]. In this work we investigate the applicability of these two algorithms to max-min and min-max partitioning of a tree for various different weighting functions. We define the families of basic and invariant weighting functions. It is shown that the first shifting algorithm yields a max-min q-partition for every basic weighting function. The second shifting algorithm yields a min-max q-partition for every invariant weighting function. In addition a modification of the second algorithm yields a min-max q-partition for the noninvariant diameter weighting function.