On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters
| Autor: | Ulrik Brandes, Svein Høgemo, Benjamin Bergougnoux, Jan Arne Telle, Christophe Paul |
|---|---|
| Přispěvatelé: | Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), ANR-17-CE23-0010,ESIGMA,Efficacité et structure pour les applications de la fouille de graphes(2017), ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016) |
| Rok vydání: | 2021 |
| Předmět: |
0102 computer and information sciences
02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Measure (mathematics) Interpretation (model theory) Vertex (geometry) Hierarchical clustering Combinatorics Ranking 010201 computation theory & mathematics Robustness (computer science) 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) Partition (number theory) 020201 artificial intelligence & image processing MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Fundamentals of Computation Theory ISBN: 9783030865924 FCT Lecture Notes in Computer Science (LNCS) 23rd International Symposium on Fundamentals of Computation Theory (FCT 2021) 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⟩ |
| DOI: | 10.1007/978-3-030-86593-1_20 |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|