A shifting algorithm for constrained min-max partition on trees

DOI10.1016/0166-218X(93)90137-DzbMath0797.68128MaRDI QIDQ686520

Ronald I. Becker, Eliezer Agasi, Yehoshua Perl

Publication date: 2 December 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmNP-completeheight-constrained min-max problempartition on treessize-constrained min-max problem

Mathematics Subject Classification ID

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

Related Items

The shifting algorithm technique for the partitioning of trees ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations ⋮ Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows ⋮ Connected graph partitioning with aggregated and non‐aggregated gap objective functions ⋮ Tree partitioning under constraints. -- Clustering for vehicle routing problems ⋮ Divider-based algorithms for hierarchical tree partitioning. ⋮ Uniform and most uniform partitions of trees ⋮ A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees ⋮ Most uniform path partitioning and its use in image processing ⋮ Min-max optimization of several classical discrete optimization problems ⋮ Efficient implementation of a shifting algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient implementation of a shifting algorithm
• Parallel concepts in graph theory
• Efficient Optimization of Monotonic Functions on Trees
• Shifting algorithms for tree partitioning with general weighting functions
• Circuit partitioning with size and connection constraints
• Max-Min Tree Partitioning
• A Shifting Algorithm for Min-Max Tree Partitioning

This page was built for publication: A shifting algorithm for constrained min-max partition on trees