A Shifting Algorithm for Min-Max Tree Partitioning

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

Research output: Contribution to journalArticlepeer-review

52 Scopus citations

Abstract

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)
Volume29
Issue number1
DOIs
StatePublished - Jan 1 1982
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Cite this