6 citations · 9 across the 8 of their papers we have counts for
13 papers
An FPT Algorithm for Diverse Minimum s-t Cuts
Krishnan Dehaleesan, Pål Grønås Drange, Fedor V. Fomin +2
We study the problem of finding a family of diverse minimum edge s-t cuts in a directed weighted graph G. Given integers k and d, the task is to decide whether G contains k minimum…
An Evaluation of Vertex Elimination Strategies for Algorithmic Differentiation
Alex Crane, Pål Grønås Drange, Eli Friedman +6
The algorithmic differentiation (AD) of mathematical functions can be interpreted as a sequence of vertex eliminations in an underlying directed acyclic graph. The problem of deter…
Structural Optimal Jacobian Accumulation and Minimum Edge Count are NP-Complete Under Vertex Elimination
Matthias Bentert, Alex Crane, Pål Grønås Drange +2
We study graph-theoretic formulations of two fundamental problems in algorithmic differentiation. The first (Structural Optimal Jacobian Accumulation) is that of computing a Jacobi…
Leveraging Fixed-Parameter Tractability for Robot Inspection Planning
Yosuke Mizutani, Daniel Coimbra Salomao, Alex Crane +5
Autonomous robotic inspection, where a robot moves through its environment and inspects points of interest, has applications in industrial settings, structural health monitoring, a…
Correlation Clustering with Vertex Splitting
Matthias Bentert, Alex Crane, Pål Grønås Drange +2
We explore Cluster Editing and its generalization Correlation Clustering with a new operation called permissive vertex splitting which addresses finding overlapping clusters in the…
Computing complexity measures of degenerate graphs
Pål Grønås Drange, Patrick Greaves, Irene Muzi +1
We show that the VC-dimension of a graph can be computed in time , where is the degeneracy of the input graph. The core idea of our algorithm is a data s…
Harmless Sets in Sparse Classes
Pål Grønås Drange, Irene Muzi, Felix Reidl
In the classic TARGET SAT SELECTION problem, we are asked to minimise the number of nodes to activate so that, after the application of a certain propagation process, all nodes of…
Fast Biclustering by Dual Parameterization
Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil +1
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 sho…
On the Threshold of Intractability
Pål Grønås Drange, Markus Sortland Dregi, Daniel Lokshtanov +1
We study the computational complexity of the graph modification problems Threshold Editing and Chain Editing, adding and deleting as few edges as possible to transform the input in…
A Polynomial Kernel for Trivially Perfect Editing
Pål Grønås Drange, Michał Pilipczuk
We give a kernel with vertices for Trivially Perfect Editing, the problem of adding or removing at most edges in order to make a given graph trivially perfect. This an…
Kernelization and Sparseness: the case of Dominating Set
Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin +9
We prove that for every positive integer and for every graph class of bounded expansion, the -Dominating Set problem admits a linear kernel on graphs from $\mat…
On the Computational Complexity of Vertex Integrity and Component Order Connectivity
Pål Grønås Drange, Markus Sortland Dregi, Pim van 't Hof
The Weighted Vertex Integrity (wVI) problem takes as input an -vertex graph , a weight function , and an integer . The task is to decide if there exis…
Exploring Subexponential Parameterized Complexity of Completion Problems
Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk +1
Let be a family of graphs. In the -Completion problem, we are given a graph and an integer as input, and asked whether at most edges can be added t…