## Search

Now showing items 1-10 of 13

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

#### Finding Induced Subgraphs via Minimal Triangulations

(Dagstuhl Publishing, 2010)

Potential maximal cliques and minimal separators are combinatorial objects
which were introduced and studied in the realm of minimal triangulation problems in- cluding
Minimum Fill-in and Treewidth. We discover unexpected ...

#### Exact algorithms for treewidth and minimum fill-in

(SIAM Journals, 2006)

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

#### A Note on Exact Algorithms for Vertex Ordering Problems on Graphs

(Springer, 2011-01-21)

In this note, we give a proof that several vertex ordering problems can be solved in O ∗(2 n ) time and O ∗(2 n ) space, or in O ∗(4 n ) time and polynomial space. The algorithms generalize algorithms for the Travelling ...

#### Parameterized complexity of the spanning tree congestion problem

(Springer, 2012-09)

We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class ...

#### Approximating Acyclicity Parameters of Sparse Hypergraphs

(Dagstuhl Publishing, 2009)

The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized ...

#### Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves

(Dagstuhl Publishing, 2009)

The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching, 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 ...

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

#### Minimum Fill-in of Sparse Graphs: Kernelization and Approximation

(Dagstuhl Publishing, 2011)

The Minimum Fill-in 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 ...