6 papers · 1 filter
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…
A Comprehensive Evaluation of Vertex Elimination Algorithms 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…
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…
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…