Journal of the ACM · 1981 · 87 citations · 5 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsData StructuresBranch And BoundCombinatorial OptimizationTree Algorithms
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.
5
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
A Linear Tree Partitioning Algorithm
Sukhamay Kundu, Jayadev Misra · SIAM Journal on Computing · 1977 · 98 citations