Show simple item record

dc.contributor.authorHøgemo, Svein
dc.contributor.authorBergougnoux, Benjamin
dc.contributor.authorBrandes, Ulrik
dc.contributor.authorPaul, Christophe
dc.contributor.authorTelle, Jan Arne
dc.date.accessioned2022-03-02T09:43:22Z
dc.date.available2022-03-02T09:43:22Z
dc.date.created2022-01-17T13:33:46Z
dc.date.issued2021
dc.identifier.issn0302-9743
dc.identifier.urihttps://hdl.handle.net/11250/2982359
dc.descriptionPostponed access: the file will be available after 2022-09-09en_US
dc.description.abstractThe 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.isoengen_US
dc.publisherSpringeren_US
dc.titleOn Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parametersen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.description.versionacceptedVersionen_US
dc.rights.holderCopyright the authors 2021en_US
cristin.ispublishedtrue
cristin.fulltextpostprint
cristin.qualitycode1
dc.identifier.doi10.1007/978-3-030-86593-1_20
dc.identifier.cristin1982562
dc.source.journalLecture Notes in Computer Science (LNCS)en_US
dc.source.pagenumber287-300en_US
dc.identifier.citationLecture Notes in Computer Science (LNCS). 2021, 12867, 287-300.en_US
dc.source.volume12867en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record