10 citations · 10 across the 3 of their papers we have counts for
5 papers
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…
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…
Parameterized Complexity of Bandwidth on Trees
Markus Sortland Dregi, Daniel Lokshtanov
The bandwidth of a -vertex graph is the smallest integer such that there exists a bijective function , called a layout of , such tha…
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…
A O(c^k n) 5-Approximation Algorithm for Treewidth
Hans Bodlaender, Pål G. Drange, Markus S. Dregi +3
We give an algorithm that for an input n-vertex graph G and integer k>0, in time 2^[O(k)]n either outputs that the treewidth of G is larger than k, or gives a tree decomposition of…