Blar i Faculty of Mathematics and Natural Sciences på forfatter "Drange, Pål Grønås"
-
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 ... -
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 ... -
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 ...