Blar i University of Bergen Library på emneord "VDP::Algoritmer og beregnbarhetsteori: 422"
Viser treff 1-2 av 2
-
Computing Complexity Measures of Degenerate Graphs
(Journal article; Peer reviewed, 2023)We show that the VC-dimension of a graph can be computed in time n^{⌈log d+1⌉} d^{O(d)}, where d is the degeneracy of the input graph. The core idea of our algorithm is a data structure to efficiently query the number of ... -
Correlation Clustering with Vertex Splitting
(Journal article; Peer reviewed, 2024)We explore CLUSTER EDITING and its generalization CORRELATION CLUSTERING with a new operation called permissive vertex splitting which addresses finding overlapping clusters in the face of uncertain information. We determine ...