## Search

Now showing items 1-6 of 6

#### 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 ...

#### B-chromatic number: Beyond NP-hardness

(Dagstuhl Publishing, 2015)

The b-chromatic number of a graph G, chi_b(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other ...

#### 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 ...

#### 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 NP-hard, none ...

#### 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 ...

#### Kernelization of Vertex Cover by Structural Parameters

(The University of Bergen, 2015-08-03)

In the NP-complete 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 ...