Browsing University of Bergen Library by Subject "VDP::Algorithms and computability theory: 422"
Now showing items 1-2 of 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 ...