Svein Høgemo

dblp:244/9568 · DBLP profile ↗
← Back
6ranked-venue papers
5as first author
4since 2021 · last 2024
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 6 · 5 first-author · 4 since 2021
YearPublicationVenuePosition
2024 Lower Bounds for Leaf Rank of Leaf Powers
Svein Høgemo
IWOCA1
2024 Tight Approximation Bounds on a Simple Algorithm for Minimum Average Search Time in Trees
Svein Høgemo
WAOA1
2022 Recognition of Linear and Star Variants of Leaf Powers is in P
Benjamin Bergougnoux, Svein Høgemo, Jan Arne Telle, Martin Vatshelle
WG2
2021 On Dasgupta's Hierarchical Clustering Objective and Its Relation to Other Graph Parameters
Svein Høgemo, Benjamin Bergougnoux, Ulrik Brandes, Christophe Paul, Jan Arne Telle
FCT1
2020 Hierarchical Clusterings of Unweighted Graphs
abstract
We study the complexity of finding an optimal hierarchical clustering of an unweighted similarity graph under the recently introduced Dasgupta objective function. We introduce a proof technique, called the normalization procedure, that takes any such clustering of a graph $G$ and iteratively improves it until a desired target clustering of G is reached. We use this technique to show both a negative and a positive complexity result. Firstly, we show that in general the problem is NP-complete. Secondly, we consider min-well-behaved graphs, which are graphs $H$ having the property that for any $k$ the graph $H(k)$ being the join of $k$ copies of $H$ has an optimal hierarchical clustering that splits each copy of $H$ in the same optimal way. To optimally cluster such a graph $H(k)$ we thus only need to optimally cluster the smaller graph $H$. Co-bipartite graphs are min-well-behaved, but otherwise they seem to be scarce. We use the normalization procedure to show that also the cycle on 6 vertices is min-well-behaved.
Svein Høgemo, Christophe Paul, Jan Arne Telle
MFCS1
2019 Linear MIM-Width of Trees
Svein Høgemo, Jan Arne Telle, Erlend Raa Vågset
WG1