Department of Informatics
Recent Submissions

Algorithmic Complexity of Clustering and LowRank Approximation Problems
(Doctoral thesis, 20210329)The two most popular unsupervised learning problems are kClustering and LowRank Approximation. Consider a set of n datapoints, in the kClustering problem, the objective is to partition these points into k clusters and ... 
ReCodLiver0.9: Overcoming Challenges in GenomeScale Metabolic Reconstruction of a Nonmodel Species
(Journal article; Peer reviewed, 202011)The availability of genome sequences, annotations, and knowledge of the biochemistry underlying metabolic transformations has led to the generation of metabolic network reconstructions for a wide range of organisms in ... 
Profiling of Small Ribosomal Subunits Reveals Modes and Regulation of Translation Initiation
(Journal article; Peer reviewed, 2020)Translation initiation is often attributed as the ratedetermining step of eukaryotic protein synthesis and key to gene expression control. Despite this centrality, the series of steps involved in this process is poorly ... 
Learning Description Logic Ontologies: Five Approaches. Where Do They Stand?
(Journal article; Peer reviewed, 2020)The quest for acquiring a formal representation of the knowledge of a domain of interest has attracted researchers with various backgrounds into a diverse field called ontology learning. We highlight classical machine ... 
Chromatin accessibility established by Pou5f3, Sox19b and Nanog primes genes for activity during zebrafish genome activation
(Journal article; Peer reviewed, 202001)In many organisms, early embryonic development is driven by maternally provided factors until the controlled onset of transcription during zygotic genome activation. The regulation of chromatin accessibility and its ... 
Subgraph Complementation
(Journal article; Peer reviewed, 202002)A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is there ... 
Fast and accurate CNNbased brushing in scatterplots
(Journal article; Peer reviewed, 2018)Brushing plays a central role in most modern visual analytics solutions and effective and efficient techniques for data selection are key to establishing a successful human‐computer dialogue. With this paper, we address ... 
Quantitative Externalization of Visual Data Analysis Results Using Local Regression Models
(Journal article; Peer reviewed, 2017)Both interactive visualization and computational analysis methods are useful for data studies and an integration of both approaches is promising to successfully combine the benefits of both methodologies. In interactive ... 
Bisection of Bounded Treewidth Graphs by Convolutions
(Journal article; Peer reviewed, 2019)In the Bisection problem, we are given as input an edgeweighted graph G. The task is to find a partition of V(G) into two parts A and B such that A  B <= 1 and the sum of the weights of the edges with one endpoint ... 
Personalized SketchBased Brushing in Scatterplots
(Journal article; Peer reviewed, 2019)Brushing is at the heart of most modern visual analytics solutions and effective and efficient brushing is crucial for successful interactive data exploration and analysis. As the user plays a central role in brushing, ... 
Complexity of the Steiner Network Problem with Respect to the Number of Terminals
(Journal article; Peer reviewed, 2019)In the Directed Steiner Network problem we are given an arcweighted digraph G, a set of terminals T subseteq V(G) with T=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H ... 
On KDEbased brushing in scatterplots and how it compares to CNNbased brushing
(Chapter, 2019)In this paper, we investigate to which degree the human should be involved into the model design and how good the empirical model can be with more careful design. To find out, we extended our previously published Mahalanobis ... 
Parameterized complexity classification of deletion to list matrixpartition for loworder matrices
(Journal article; Peer reviewed, 2019)Given a symmetric l x l matrix M=(m_{i,j}) with entries in {0,1,*}, a graph G and a function L : V(G)  > 2^{[l]} (where [l] = {1,2,...,l}), a list Mpartition of G with respect to L is a partition of V(G) into l parts, ... 
Balanced judicious bipartition is fixedparameter tractable
(Journal article; Peer reviewed, 2019)The family of judicious partitioning problems, introduced by Bollobás and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of ... 
Packing cycles faster than ErdosPosa
(Journal article; Peer reviewed, 2019)The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertexdisjoint cycles. Since the publication of the classic ErdösPósa theorem in 1965, this problem received significant attention ... 
Rank vertex cover as a natural problem for algebraic compression
(Journal article; Peer reviewed, 2019)The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a longstanding, notorious open problem in parameterized complexity. Some years ago, the breakthrough work by Kratsch and ... 
Packing arcdisjoint cycles in tournaments
(Journal article; Peer reviewed, 2019)A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining ... 
Parameterized complexity of conflictfree matchings and paths
(Journal article; Peer reviewed, 2019)An input to a conflictfree variant of a classical problem Gamma, called ConflictFree Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to ConflictFree Gamma in (I,H) ... 
Connecting the Dots (with Minimum Crossings)
(Journal article; Peer reviewed, 2019)We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertexlabeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection ... 
Parameterized streaming algorithms for minones dSAT
(Journal article; Peer reviewed, 2019)In this work, we initiate the study of the MinOnes dSAT problem in the parameterized streaming model. An instance of the problem consists of a dCNF formula F and an integer k, and the objective is to determine if F has ...