Browsing Department of Informatics by Subject "Kernelization"
Now showing items 14 of 4

Kernel(s) for Problems with No Kernel: On OutTrees with Many Leaves
(Dagstuhl Publishing, 2009)The {\sc $k$Leaf OutBranching} problem is to find an outbranching, 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 Fillin of Sparse Graphs: Kernelization and Approximation
(Dagstuhl Publishing, 2011)The Minimum Fillin 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, 201401)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 2disjoint connected subgraphs problem faster than 2ⁿ
(Springer, 201410)The 2DISJOINT 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