An efficient implementation of the shifting algorithm  for min-max tree partitioning is given. The complexity is reduced from ORk3 + kn) to O(Rk(k + log d) + n) where a tree of n vertices, radius, of R edges, and maximum degree d is partitioned into k + 1 subtrees. The improvement is mainly due to the new junction tree data structure which suggests a succinct representation for subsets of edges, of a given tree, that preserves the interrelation betqween the edges on the tree.
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics