Skip to Main content Skip to Navigation
Conference papers

On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03438654
Contributor : Christophe Paul Connect in order to contact the contributor
Submitted on : Sunday, November 21, 2021 - 8:46:23 PM
Last modification on : Tuesday, November 23, 2021 - 3:46:29 AM

Links full text

Identifiers

Collections

Citation

Svein Høgemo, Benjamin Bergougnoux, Ulrik Brandes, Christophe Paul, Jan Arne Telle. On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters. 23rd International Symposium on Fundamentals of Computation Theory (FCT 2021), Sep 2021, Athens, Greece. pp.287-300, ⟨10.1007/978-3-030-86593-1_20⟩. ⟨lirmm-03438654⟩

Share

Metrics

Record views

5