Now showing items 1-4 of 4

• #### Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves ﻿

(Dagstuhl Publishing, 2009)
The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least $k$ leaves in a given digraph. The problem has recently received much attention from the viewpoint ...
Conference object
• #### Minimum Fill-in of Sparse Graphs: Kernelization and Approximation ﻿

(Dagstuhl Publishing, 2011)
The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. The problem has important applications in numerical algebra, in particular in sparse matrix computations. We develop ...
Conference object
• #### Parameterized complexity of Eulerian deletion problems ﻿

(Springer, 2014-01)
We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity ...
Journal article
• #### Solving the 2-disjoint connected subgraphs problem faster than 2ⁿ ﻿

(Springer, 2014-10)
The 2-DISJOINT CONNECTED SUBGRAPHS problem, given a graph along with two disjoint sets of terminals Z1,Z2, asks whether it is possible to find disjoint sets A1,A2, such that Z1 ⊆ A1, Z2 ⊆ A2 and A1,A2 induce connected ...
Journal article