Optimal Parametric Search for Path and Tree Partitioning

Greg N. Frederickson, Samson Zhou

We present linear-time algorithms for partitioning a path or a tree with weights on the vertices by removing $k$ edges to maximize the minimum-weight component. We also use the sam…