Browsing Bergen Open Research Archive by Author "Reidl, Felix"

Now showing items 1-2 of 2

    • 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 ...

    • Fast biclustering by dual parameterization 

      Drange, Pål Grønås; Reidl, Felix; Villaamil, Fernando Sánchez; Sikdar, Somnath (Peer reviewed; Journal article, 2015)
      We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NP-hard, none ...