dc.contributor.author | Høgemo, Svein | |
dc.contributor.author | Bergougnoux, Benjamin | |
dc.contributor.author | Brandes, Ulrik | |
dc.contributor.author | Paul, Christophe | |
dc.contributor.author | Telle, Jan Arne | |
dc.date.accessioned | 2022-03-02T09:43:22Z | |
dc.date.available | 2022-03-02T09:43:22Z | |
dc.date.created | 2022-01-17T13:33:46Z | |
dc.date.issued | 2021 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.uri | https://hdl.handle.net/11250/2982359 | |
dc.description.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. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Springer | en_US |
dc.title | On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | acceptedVersion | en_US |
dc.rights.holder | Copyright the authors 2021 | en_US |
cristin.ispublished | true | |
cristin.fulltext | postprint | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.1007/978-3-030-86593-1_20 | |
dc.identifier.cristin | 1982562 | |
dc.source.journal | Lecture Notes in Computer Science (LNCS) | en_US |
dc.source.pagenumber | 287-300 | en_US |
dc.identifier.citation | Lecture Notes in Computer Science (LNCS). 2021, 12867, 287-300. | en_US |
dc.source.volume | 12867 | en_US |