Blar i University of Bergen Library på emneord "VDP::Algoritmer og beregnbarhetsteori: 422"
Viser treff 1-1 av 1
-
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 ...