• 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 ...
    • Correlation Clustering with Vertex Splitting 

      Bentert, Matthias; Crane, Alex; Drange, Pål Grønås; Reidl, Felix; Sullivan, Blair D. (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 ...