A Shifting Algorithm for Min-Max Tree Partitioning

DOI10.1145/322290.322294MaRDI QIDQ3933759zbMATH OpenOpenAlexFDO

Authors 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

top-down shifting algorithmtree partitioning

Mathematics Subject Classification ID

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

Cited in

(27)

• Efficient implementation of a shifting algorithm
• Path equipartition in the Chebyshev norm
• 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
• A linear-time algorithm for finding an edge-partition with max-min ratio at most two
• Partitioning a graph into balanced connected classes: formulations, separation and experiments
• Approximation algorithms for the maximally balanced connected graph tripartition problem
• 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
• Cardinality constrained connected balanced partitions of trees under different criteria
• A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees
• Improved algorithms for path partition and related problems
• BALANCED PARTITION OF MINIMUM SPANNING TREES
• Dispersion on trees
• Approximation algorithms for maximally balanced connected graph partition
• A tight bound on the min-ratio edge-partitioning problem of a tree
• Approximation and parameterized algorithms for balanced connected partition problems
• Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows
• Balanced connected partitions of graphs: approximation, parameterization and lower bounds
• Connected graph partitioning with aggregated and non‐aggregated gap objective functions
• A shifting algorithm for constrained min-max partition on trees
• Balanced connected graph partition
• Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3933759)