Max-Min Tree Partitioning
From MaRDI portal
Publication:3902511
DOI10.1145/322234.322236zbMath0454.68068OpenAlexW1970194957MaRDI QIDQ3902511
Stephen R. Schach, Yehoshua Perl
Publication date: 1981
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322234.322236
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)
Related Items (36)
Balanced connected graph partition ⋮ Tree edge decomposition with an application to minimum ultrametric tree approximation ⋮ On the uniform edge-partition of a tree ⋮ FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS ⋮ An overview of graph covering and partitioning ⋮ The shifting algorithm technique for the partitioning of trees ⋮ Partitioning a matrix to minimize the maximum cost ⋮ A tight bound on the min-ratio edge-partitioning problem of a tree ⋮ Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs ⋮ Max-min weight balanced connected partition ⋮ Approximation and parameterized algorithms for balanced connected partition problems ⋮ Cardinality constrained connected balanced partitions of trees under different criteria ⋮ Balanced connected partitions of graphs: approximation, parameterization and lower bounds ⋮ Connected graph partitioning with aggregated and non‐aggregated gap objective functions ⋮ A linear-time algorithm for finding an edge-partition with max-min ratio at most two ⋮ Divider-based algorithms for hierarchical tree partitioning. ⋮ Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size ⋮ Algorithms for uniform centered partitions of trees ⋮ A shifting algorithm for constrained min-max partition on trees ⋮ Uniform and most uniform partitions of trees ⋮ Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches ⋮ A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees ⋮ Partitioning a graph into balanced connected classes: formulations, separation and experiments ⋮ Approximation algorithms for maximally balanced connected graph partition ⋮ Unnamed Item ⋮ Most uniform path partitioning and its use in image processing ⋮ PARTITIONING TREES OF SUPPLY AND DEMAND ⋮ On a 2-dimensional equipartition problem ⋮ Unnamed Item ⋮ Path equipartition in the Chebyshev norm ⋮ Continuous bottleneck tree partitioning problems ⋮ Approximation algorithms for the maximally balanced connected graph tripartition problem ⋮ Approximations to clustering and subgraph problems on trees ⋮ A shifting algorithm for continuous tree partitioning ⋮ On the complexity of partitioning graphs into connected subgraphs ⋮ Efficient implementation of a shifting algorithm
This page was built for publication: Max-Min Tree Partitioning
