Efficient implementation of a shifting algorithm
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.
- A shifting algorithm for constrained min-max partition on trees
- New Upper Bounds on Continuous Tree Edge-Partition Problem
- The shifting algorithm technique for the partitioning of trees
- scientific article; zbMATH DE number 3866593
- A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees
- A Linear Tree Partitioning Algorithm
- A shifting algorithm for constrained min-max partition on trees
- A Shifting Algorithm for Min-Max Tree Partitioning
- An Algorithmic Approach to Network Location Problems. II: Thep-Medians
- Max-Min Tree Partitioning
- Shifting algorithms for tree partitioning with general weighting functions
- Divider-based algorithms for hierarchical tree partitioning.
- Accelerated shift-and-add algorithms
- Uniform and most uniform partitions of trees
- Most uniform path partitioning and its use in image processing
- On a 2-dimensional equipartition problem
- Continuous bottleneck tree partitioning problems
- A shifting algorithm for continuous tree partitioning
- The shifting algorithm technique for the partitioning of trees
- Partitioning a matrix to minimize the maximum cost
- A linear-time algorithm for finding an edge-partition with max-min ratio at most two
- Minmax subtree cover problem on cacti
- Algorithms for uniform centered partitions of trees
- Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows
- A shifting algorithm for constrained min-max partition on trees
This page was built for publication: Efficient implementation of a shifting algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1070825)