### Recent Submissions

• #### The Ontology Lookup Service: bigger and better ﻿

(Oxford University Press, 2010-05-11)
The Ontology Lookup Service (OLS; http://www.ebi .ac.uk/ols) has been providing several means to query, browse and navigate biomedical ontologies and controlled vocabularies since it first went into production 4 years ...
Journal article
• #### Enumerating minimal connected dominating sets in graphs of bounded chordality ﻿

(Dagstuhl Publishing, 2015)
Listing, generating or enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration ...
Conference object
• #### 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, ...
Conference object
• #### The Proteomics Identifications database: 2010 update ﻿

(Oxford University Press (OUP), 2009-11-11)
The Proteomics Identifications database (PRIDE, <a href="http://www.ebi.ac.uk/pride"target="blank">http://www.ebi.ac.uk/pride) at the European Bioinformatics Institute has become one of the main repositories of mass ...
Journal article
• #### Chromatin and epigenetic features of long-range gene regulation ﻿

(Oxford University Press (OUP), 2013-06-13)
The precise regulation of gene transcription during metazoan development is controlled by a complex system of interactions between transcription factors, histone modifications and modifying enzymes and chromatin conformation. ...
Journal article
• #### 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 ...
Conference object
• #### The EMBRACE web service collection ﻿

(Oxford University Press (OUP), 2010-05-10)
The EMBRACE (European Model for Bioinformatics Research and Community Education) web service collection is the culmination of a 5-year project that set out to investigate issues involved in developing and deploying web ...
Journal article
• #### The Genomic HyperBrowser: an analysis web server for genome-scale data ﻿

(Oxford University Press (OUP), 2013-04-30)
The immense increase in availability of genomic scale datasets, such as those provided by the ENCODE and Roadmap Epigenomics projects, presents unprecedented opportunities for individual researchers to pose novel falsifiable ...
Journal article
• #### Variants of plane diameter completion ﻿

(Dagstuhl Publishing, 2015)
The Plane Diameter Completion problem asks, given a plane graph G and a positive integer d, if it is a spanning subgraph of a plane graph H that has diameter at most d. We examine two variants of this problem where the ...
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
• #### 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 ...
Conference object
• #### 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 ...
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
• #### Finding even subgraphs even faster ﻿

(Dagstuhl Publishing, 2015)
Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k ...
Conference object
• #### Maximum matching width: New characterizations and a fast algorithm for dominating set ﻿

(Dagstuhl Publishing, 2015)
We give alternative definitions for maximum matching width, e.g., a graph G has mmw(G) <= k if and only if it is a subgraph of a chordal graph H and for every maximal clique X of H there exists A,B,C \subseteq X with A ...
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 NP-hard, none ...
Conference object
• #### 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
• #### 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 ...
Conference object
• #### 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 ...
Conference object
• #### 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 ...
Conference object