The minimum height of vertex and edge partition trees are well-studied graph parameters known as, for instance, vertex and edge ranking number. While they are NP-hard to determine in general, linear-time algorithms exist for trees. Motivated by a correspondence with Dasgupta's objective for hierarchical clustering we consider the total rather than maximum depth of vertices as an alternative objective for minimization. For vertex partition trees this leads to a new parameter with a natural interpretation as a measure of robustness against vertex removal. As tools for the study of this family of parameters we show that they have similar recursive expressions and prove a binary tree rotation lemma. The new parameter is related to trivially perfect graph completion and therefore intractable like the other three are known to be. We give polynomial-time algorithms for both total-depth variants on caterpillars and on trees with a bounded number of leaf neighbors. For general trees, we obtain a 2-approximation algorithm.
翻译:顶端和边缘分区树的最低高度是人们研究周密的图形参数,例如,顶端和边缘排位数。 虽然它们很难确定, 但一般而言, 树的线性时间算法是存在的。 基于与 Dasgupta 的分层组合目标的通信, 我们将脊椎的总高度而不是最大深度视为一个可以最小化的替代目标。 对于顶端分区树, 这导致一个新的参数, 以自然解释作为衡量顶端清除的稳健度的尺度。 作为研究这一系列参数的工具, 我们发现它们具有相似的递归表达法, 并证明它们是一个双树旋转的利玛。 新的参数与极不完美的图形完成有关, 因此已知与其他三种相似的复杂性是已知的 。 我们给出了全深度的圆柱形和树木的多元时间算法, 上面的叶邻居众多。 对于普通树, 我们得到了一种2 配方的算法 。