Zur Kurzanzeige

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
 Printexemplar via ETH-Bibliothek suchen

Dateien zu diesem Eintrag

DateienGrößeFormatIm Viewer öffnen

Zu diesem Eintrag gibt es keine Dateien.

Publikationstyp

Zur Kurzanzeige