Max-Min Tree Partitioning

Yehoshua Perl, Stephen R. Schach

Research output: Contribution to journalArticlepeer-review

63 Scopus citations

Abstract

The max-rain k-partition algorithm may be formulated as follows: Given a tree T with n edges and a nonnegative weight associated with each vertex, assign a cut to each of k distinct edges of T so as to maximize the weight of the lightest resulting connected subtree. An algorithm for this problem is presented which initially assigns all k cuts to one edge incident with a terminal vertex of T; thereafter the cuts are shifted from edge to adjacent edge on the basis of local information. An efficient implementation with complexity O(k 2. rd(T) + kn), where rd(T) is the number of edges in the radius of T, is described. An algorithm for a simpler problem, namely, the partitioning of Tinto the maximum number of connected components whose weight is bounded below, is then described. Combined with the technique of binary search, it yields an alternative algorithm for the max-rain k-partition problem with complexity dependent on the range of the given weights.

Original languageEnglish (US)
Pages (from-to)5-15
Number of pages11
JournalJournal of the ACM (JACM)
Volume28
Issue number1
DOIs
StatePublished - Jan 1 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Fingerprint

Dive into the research topics of 'Max-Min Tree Partitioning'. Together they form a unique fingerprint.

Cite this