A Shifting Algorithm for Min-Max Tree Partitioning

DOI10.1145/322290.322294zbMath0477.68066OpenAlexW1971764118MaRDI QIDQ3933759

Stephen R. Schach, Yehoshua Perl, Ronald I. Becker

Publication date: 1982

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322290.322294

zbMATH Keywords

tree partitioningtop-down shifting algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (27)

Balanced connected graph partition ⋮ Tree edge decomposition with an application to minimum ultrametric tree approximation ⋮ On the uniform edge-partition of a tree ⋮ A subexponential algorithm for the coloured tree partition problem ⋮ Two new algorithms for the min-power broadcast problem in static ad hoc networks ⋮ BALANCED PARTITION OF MINIMUM SPANNING TREES ⋮ A tight bound on the min-ratio edge-partitioning problem of a tree ⋮ Improved algorithms for path partition and related problems ⋮ Approximation and parameterized algorithms for balanced connected partition problems ⋮ Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows ⋮ 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 ⋮ A shifting algorithm for constrained min-max partition on 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 ⋮ On a 2-dimensional equipartition problem ⋮ Path equipartition in the Chebyshev norm ⋮ Continuous bottleneck tree partitioning problems ⋮ Approximation algorithms for the maximally balanced connected graph tripartition problem ⋮ A shifting algorithm for continuous tree partitioning ⋮ Efficient implementation of a shifting algorithm

This page was built for publication: A Shifting Algorithm for Min-Max Tree Partitioning