Blar i Department of Informatics på emneord "Parameterized complexity"
Viser treff 1-8 av 8
-
B-chromatic number: Beyond NP-hardness
(Peer reviewed; Journal article, 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 ... -
Connecting Vertices by Independent Trees
(Journal article; Peer reviewed, 2014)We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T1, . . . , Ts of G are completely independent spanning trees of U if each of them contains U , and ... -
Fast biclustering by dual parameterization
(Peer reviewed; Journal article, 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 ... -
Kernelization of Vertex Cover by Structural Parameters
(Master thesis, 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 ... -
On cutwidth parameterized by vertex cover
(Peer reviewed; Journal article, 2014-04)We study the CUTWIDTH problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two ... -
Parameterized complexity of secluded connectivity problems
(Peer reviewed; Journal article, 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 ... -
Subexponential Algorithms for Partial Cover Problems
(Peer reviewed; Journal article, 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 ... -
Tight bounds for parameterized complexity of Cluster Editing
(Peer reviewed; Journal article, 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 ...