Markus S. Dregi

activity

20132015

most citedA O(c^k n) 5-Approximation Algorithm for Treewidth

10 citations · 10 across the 3 of their papers we have counts for

collaborators

Showing 2014Show all

3 papers · 1 filter

cs.DS2014

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 $r$ and for every graph class $G$ of bounded expansion, the $r$ -Dominating Set problem admits a linear kernel on graphs from $\mat…

cs.DS2014

Parameterized Complexity of Bandwidth on Trees

Markus Sortland Dregi, Daniel Lokshtanov

The bandwidth of a $n$ -vertex graph $G$ is the smallest integer $b$ such that there exists a bijective function $f : V (G) \to {1, ..., n}$ , called a layout of $G$ , such tha…

cs.DS2014

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 $n$ -vertex graph $G$ , a weight function $w : V (G) \to N$ , and an integer $p$ . The task is to decide if there exis…