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 language | English (US) |
|---|---|
| Pages (from-to) | 58-67 |
| Number of pages | 10 |
| Journal | Journal of the ACM (JACM) |
| Volume | 29 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 1 1982 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Artificial Intelligence
- Information Systems
- Control and Systems Engineering
- Hardware and Architecture
Keywords
- mm-max partition
- shifting algorithm
- tree partmomng