Continuous bottleneck tree partitioning problems
We study continuous partitioning problems on tree network spaces whose edges and nodes are points in Euclidean spaces. A continuous partition of this space into p connected components is a collection of p subtrees, such that no pair of them intersect at more than one point, and their union is the tree space. An edge-partition is a continuous partition defined by selecting p?1 cut points along the edges of the underlying tree, which is assumed to have n nodes. These cut points induce a partition into p subtrees (connected components). The objective is to minimize (maximize) the maximum (minimum) size of the components (the minmax (maxmin) problem). When the size is the length of a subtree, the minmax and the maxmin partitioning problems are NP-hard. We present algorithms for the edge-partitioning versions of the problem. When the size is the diameter, the minmax problems coincide with the continuous p-center problem. We describe and algorithms for the maxmin partitioning and edge-partitioning problems, respectively, where the size is the diameter of a component.
tree partitioning continuous p-center problems bottleneck problems parametric search