A Shifting Algorithm for Min-Max Tree Partitioning

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

Research output: Contribution to journalArticlepeer-review

59 Scopus citations


The problem of finding a mm-max partmon of a weJghted tree T with n veruces into q subtrees by means of k = q - 1 cuts is considered. A top-down shifting algorithm for this problem ts presented An outhne is given of an efficJent implementatmn of the algorithm wtth complexity O(k3rd(T) + kn), where rd(T) ts the number of edges m the radius of T.

Original languageEnglish (US)
Pages (from-to)58-67
Number of pages10
JournalJournal of the ACM (JACM)
Issue number1
StatePublished - Jan 1 1982
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence
  • Information Systems
  • Control and Systems Engineering
  • Hardware and Architecture


  • mm-max partition
  • shifting algorithm
  • tree partmomng

Cite this