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

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)

Cited in

(27)

• A shifting algorithm for constrained min-max partition on trees
• Balanced connected graph partition
• Improved algorithms for path partition and related problems
• Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches
• Continuous bottleneck tree partitioning problems
• Cardinality constrained connected balanced partitions of trees under different criteria
• Path equipartition in the Chebyshev norm
• BALANCED PARTITION OF MINIMUM SPANNING TREES
• Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows
• Partitioning a graph into balanced connected classes: formulations, separation and experiments
• Connected graph partitioning with aggregated and non‐aggregated gap objective functions
• A tight bound on the min-ratio edge-partitioning problem of a tree
• Most uniform path partitioning and its use in image processing
• A subexponential algorithm for the coloured tree partition problem
• Tree edge decomposition with an application to minimum ultrametric tree approximation
• Two new algorithms for the min-power broadcast problem in static ad hoc networks
• On a 2-dimensional equipartition problem
• A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees
• A shifting algorithm for continuous tree partitioning
• A linear-time algorithm for finding an edge-partition with max-min ratio at most two
• Approximation algorithms for the maximally balanced connected graph tripartition problem
• Approximation algorithms for maximally balanced connected graph partition
• Dispersion on trees
• On the uniform edge-partition of a tree
• Approximation and parameterized algorithms for balanced connected partition problems
• Balanced connected partitions of graphs: approximation, parameterization and lower bounds
• Efficient implementation of a shifting algorithm

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)