Browsing Bergen Open Research Archive by Author "Greaves, Patrick"
Now showing items 1-1 of 1
-
Computing Complexity Measures of Degenerate Graphs
Drange, Pål Grønås; Greaves, Patrick; Muzi, Irene; Reidl, Felix (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 ...