@InProceedings{10.1007/978-981-95-0218-9_5,
author="Luo, Ruixi
and Zhu, Taikun
and Jin, Kai",
editor="Fomin, Fedor V.
and Xiao, Mingyu",
title="Sum-of-Max Chain Partition of a Tree",
booktitle="Computing and Combinatorics",
year="2026",
publisher="Springer Nature Singapore",
address="Singapore",
pages="53--67",
abstract="Path partition problems on trees have found various applications. In this paper, we present an {\$}{\$}O(n {\backslash}log n){\$}{\$}O(nlogn)time algorithm for solving the following variant of path partition problem: given a rooted tree of n nodes {\$}{\$}1, {\backslash}ldots , n{\$}{\$}1,{\ldots},n, where vertex i is associated with a weight {\$}{\$}w{\_}i{\$}{\$}wiand a cost {\$}{\$}s{\_}i{\$}{\$}si, partition the tree into several disjoint chains {\$}{\$}C{\_}1,{\backslash}ldots ,C{\_}k{\$}{\$}C1,{\ldots},Ck, so that the weight of each chain is no more than a threshold {\$}{\$}w{\_}0{\$}{\$}w0and the sum of the largest {\$}{\$}s{\_}i{\$}{\$}siin each chain is minimized. We also generalize the algorithm to the case where the cost of a chain is determined by the {\$}{\$}s{\_}i{\$}{\$}siof the vertex with the highest rank in the chain, which can be determined by an arbitrary total order defined on all nodes instead of the value of {\$}{\$}s{\_}i{\$}{\$}si.",
isbn="978-981-95-0218-9"
}