Recently two shifting algorithms were designed for two optimum tree partitioning problems: The problem of max-min q-partition  and the problem of min-max q-partition . 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.
All Science Journal Classification (ASJC) codes
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics