Browsing Department of Informatics by Subject "parameterized complexity"
Now showing items 16 of 6

Bchromatic number: Beyond NPhardness
(Dagstuhl Publishing, 2015)The bchromatic number of a graph G, chi_b(G), is the largest integer k such that G has a kvertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other ...Conference object 
Fast biclustering by dual parameterization
(Dagstuhl Publishing, 2015)We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NPhard, none ...Conference object 
Kernelization of Vertex Cover by Structural Parameters
(The University of Bergen, 20150803)In the NPcomplete problem Vertex Cover, one is given a graph G and an integer k and are asked whether there exists a vertex set S ⊆ V (G) with size at most k such that every edge of the graph is incident to a vertex in ...Master thesis 
Parameterized complexity of secluded connectivity problems
(Dagstuhl Publishing, 2015)The Secluded Path problem introduced by Chechik et al. in [ESA 2013] models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of ...Conference object 
Subexponential Algorithms for Partial Cover Problems
(Dagstuhl Publishing, 2009)Partial Cover problems are optimization versions of fundamental and well studied problems like {\sc Vertex Cover} and {\sc Dominating Set}. Here one is interested in covering (or dominating) the maximum number of edges (or ...Conference object 
Tight bounds for parameterized complexity of Cluster Editing
(Dagstuhl Publishing, 2013)In the Correlation Clustering problem, also known as Cluster Editing, we are given an undirected graph G and a positive integer k; the task is to decide whether G can be transformed into a cluster graph, i.e., a disjoint ...Conference object