Efficient implementation of a shifting algorithm (Q1070825): Difference between revisions

Let T be an undirected node-weighted tree. The \(\min\)-max-(k\(+1)\)- partition problem is to remove k edges of T such that \(\max_{1\leq i\leq k+1}w(T_ i)\) is minimized, where the \(T_ i\) are the remaining connected components of T and where \(w(T_ i)\) is the sum of the node- weights of \(T_ i\). An implementation of time complexity \(O(Rk(k+\log d)+n)\) of the shifting algorithm given in the paper of \textit{R. I. Becker}, \textit{Y. Perl} and \textit{S. R. Schach} in J. Assoc. Comput. Mach. 29, 58-67 (1982; Zbl 0477.68066) is described. Here r is the radius of T, and d is the maximum degree of any vertex in T.