On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters
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.contributor.editor
Bampis, Evripidis
dc.contributor.editor
Pagourtzis, Aris
dc.date.accessioned
2021-10-04T12:49:18Z
dc.date.available
2021-09-30T14:39:11Z
dc.date.available
2021-10-04T12:49:18Z
dc.date.issued
2021-01
dc.identifier.isbn
978-3-030-86592-4
en_US
dc.identifier.isbn
978-3-030-86593-1
en_US
dc.identifier.issn
0302-9743
dc.identifier.issn
1611-3349
dc.identifier.other
10.1007/978-3-030-86593-1_20
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/507807
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
en
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
Conference Paper
dc.date.published
2021-09-09
ethz.book.title
Fundamentals of Computation Theory
en_US
ethz.journal.title
Lecture Notes in Computer Science
ethz.journal.volume
12867
en_US
ethz.journal.abbreviated
LNCS
ethz.pages.start
287
en_US
ethz.pages.end
300
en_US
ethz.event
23rd International Symposium on Fundamentals of Computation Theory (FCT 2021)
en_US
ethz.event.location
Online
en_US
ethz.event.date
September 12-15, 2021
en_US
ethz.identifier.wos
ethz.publication.place
Cham
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02045 - Dep. Geistes-, Sozial- u. Staatswiss. / Dep. of Humanities, Social and Pol.Sc.::09610 - Brandes, Ulrik / Brandes, Ulrik
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02045 - Dep. Geistes-, Sozial- u. Staatswiss. / Dep. of Humanities, Social and Pol.Sc.::09610 - Brandes, Ulrik / Brandes, Ulrik
en_US
ethz.date.deposited
2021-09-30T14:39:20Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-10-04T12:49:32Z
ethz.rosetta.lastUpdated
2022-03-29T14:02:59Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=On%20Dasgupta%E2%80%99s%20Hierarchical%20Clustering%20Objective%20and%20Its%20Relation%20to%20Other%20Graph%20Parameters&rft.jtitle=Lecture%20Notes%20in%20Computer%20Science&rft.date=2021-01&rft.volume=12867&rft.spage=287&rft.epage=300&rft.issn=0302-9743&1611-3349&rft.au=H%C3%B8gemo,%20Svein&Bergougnoux,%20Benjamin&Brandes,%20Ulrik&Paul,%20Christophe&Telle,%20Jan%20Arne&rft.isbn=978-3-030-86592-4&978-3-030-86593-1&rft.genre=proceeding&rft_id=info:doi/10.1007/978-3-030-86593-1_20&rft.btitle=Fundamentals%20of%20Computation%20Theory
Dateien zu diesem Eintrag
Dateien | Größe | Format | Im Viewer öffnen |
---|---|---|---|
Zu diesem Eintrag gibt es keine Dateien. |
Publikationstyp
-
Conference Paper [35284]