Browsing Bergen Open Research Archive by Author "Drange, Pål Grønås"

Now showing items 1-9 of 9

    • Cluster Editing with Overlapping Communities 

      Arrighi, Emmanuel Jean Paul Pierre; Bentert, Matthias; Drange, Pål Grønås; Sullivan, Blair D.; Wolf, Petra Henrike Karola (Journal article; Peer reviewed, 2023)
      Cluster Editing, also known as correlation clustering, is a well-studied graph modification problem. In this problem, one is given a graph and allowed to perform up to k edge additions and deletions to transform it into a ...

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

    • Exploring Subexponential Parameterized Complexity of Completion Problems 

      Drange, Pål Grønås; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve (Peer reviewed; Journal article, 2014-02-19)
      Let F be a family of graphs. In the F-Completion problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the resulting graph does not contain a graph ...

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

    • PACE Solver Description: LUNCH - Linear Uncrossing Heuristics 

      Langedal, Kenneth; Bentert, Matthias; Blanco, Thorgal; Drange, Pål Grønås (Journal article; Peer reviewed, 2024)
      The 2024 PACE challenge is on One-Sided Crossing Minimization: Given a bipartite graph with one fixed and one free layer, compute an ordering of the vertices in the free layer that minimizes the number of edge crossings ...

    • Parameterized Graph Modification Algorithms 

      Drange, Pål Grønås (Doctoral thesis, 2015-12-10)
      Graph modification problems form an important class of algorithmic problems in computer science. In this thesis, we study edge modification problems towards classes related to chordal graphs, with the main focus on trivially ...

    • A survey of parameterized algorithms and the complexity of edge modification 

      Crespelle, Christophe; Drange, Pål Grønås; Fomin, Fedor; Golovach, Petr (Journal article; Peer reviewed, 2023)
      The survey is a comprehensive overview of the developing area of parameterized algorithms for graph modification problems. It describes state of the art in kernelization, subexponential algorithms, and parameterized ...

    • Two-Sets Cut-Uncut on Planar Graphs 

      Bentert, Matthias; Drange, Pål Grønås; Fomin, Fedor; Golovach, Petr; Korhonen, Tuukka (Journal article; Peer reviewed, 2024)
      We study Two-Sets Cut-Uncut on planar graphs. Therein, one is given an undirected planar graph G and two disjoint sets S and T of vertices as input. The question is, what is the minimum number of edges to remove from G, ...