## Search

Now showing items 1-9 of 9

#### Tournaments and Optimality: New Results in Parameterized Complexity

(The University of Bergen, 2013-11-22)

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

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

#### Exploring Subexponential Parameterized Complexity of Completion Problems

(Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014-02-19)

Let F be a family of graphs. In the F-Completion problem, we are given an n-vertex graph
G and an integer k as input, and asked whether at most k edges can be added to G so that the
resulting graph does not contain a ...

#### Subexponential-time parameterized algorithm for Steiner tree on planar graphs

(Dagstuhl Publishing, 2013)

The well-known bidimensionality theory provides a method for designing fast, subexponential-time parameterized algorithms for a vast number of NP-hard problems on sparse graph classes such as planar graphs, bounded genus ...

#### Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings

(Dagstuhl Publishing, 2013)

The notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semi-complete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, ...

#### Largest chordal and interval subgraphs faster than 2n

(Springer, 2015-08-22)

We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time O(2λn) for some λ< 1. These are the first algorithms breaking the trivial 2nnO(1) ...

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

#### On cutwidth parameterized by vertex cover

(Springer, 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 ...