Department of Informatics
Recent Submissions

Structural parameterizations of clique coloring
(Journal article; Peer reviewed, 2020)A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether ... 
The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope
(Chapter, 2021)Given an undirected graph G = (V, E) and an integer k∈{1,…,V} , we initiate the combinatorial study of stable sets of cardinality exactly k in G. Our aim is to instigate the polyhedral investigation of the convex hull ... 
On the Tractability of Optimization Problems on HGraphs
(Journal article; Peer reviewed, 2020)For a graph H, a graph G is an Hgraph if it is an intersection graph of connected subgraphs of some subdivision of H. Hgraphs naturally generalize several important graph classes like interval graphs or circulararc ... 
Compressing permutation groups into grammars and polytopes. A graph embedding approach
(Journal article; Peer reviewed, 2020)It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+G) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can ... 
One byte at a time: evidencing the quality of clinical service nextgeneration sequencing for germline and somatic variants
(Journal article; Peer reviewed, 2020)Nextgeneration sequencing (NGS) is replacing other molecular techniques to become the de facto gene diagnostics approach, transforming the speed of diagnosis for patients and expanding opportunities for precision medicine. ... 
Visception: An Interactive Visual Framework for Nested Visualization Design
(Journal article; Peer reviewed, 2020)Nesting is the embedding of charts into the marks of another chart. Related to principles such as Tufte’s rule of utilizing micro/macro readings, nested visualizations have been employed to increase information density, ... 
A BitVector Differential Model for the Modular Addition by a Constant
(Journal article; Peer reviewed, 2020)ARX algorithms are a class of symmetrickey algorithms constructed by Addition, Rotation, and XOR, which achieve the best software performances in lowend microcontrollers. To evaluate the resistance of an ARX cipher against ... 
Transversals of longest paths
(Journal article; Peer reviewed, 202003)Let lpt(G) be the minimum cardinality of a transversal of longest paths in G, that is, a set of vertices that intersects all longest paths in a graph G. There are several results in the literature bounding the value of ... 
A Polynomial Kernel for Line Graph Deletion
(Journal article; Peer reviewed, 2020)The line graph of a graph G is the graph L(G) whose vertex set is the edge set of G and there is an edge between e,f ∈ E(G) if e and f share an endpoint in G. A graph is called line graph if it is a line graph of some ... 
Reconstructing ribosomal genes from large scale total RNA metatranscriptomic data
(Journal article; Peer reviewed, 20200313)Motivation Technological advances in metatranscriptomics have enabled a deeper understanding of the structure and function of microbial communities. ‘Total RNA’ metatranscriptomics, sequencing of total reverse transcribed ... 
Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
(Journal article; Peer reviewed, 2020)Given a vertexcolored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertexconnected if there is a rainbow vertex path between every pair of its ... 
A complexity dichotomy for critical values of the bchromatic number of graphs
(Journal article; Peer reviewed, 2020)A bcoloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The bColoring problem asks whether a graph G has ... 
Reducing Graph Transversals via Edge Contractions
(Journal article; Peer reviewed, 2020)For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least ... 
Statistical considerations for the design and interpretation of proteomics experiments
(Doctoral thesis, 20210610)The methods to study proteins are continuously improving, making it possible to identify and study increasingly more proteins. It is important to keep studying and improving the way experiments are designed, performed, and ... 
Geometric Planar Networks on Bichromatic Points
(Journal article; Peer reviewed, 2020)We study four classical graph problems – Hamiltonian path, Traveling salesman, Minimum spanning tree, and Minimum perfect matching on geometric graphs induced by bichromatic ( Open image in new window and Open image in new ... 
Metagenomeassembled genome distribution and key functionality highlight importance of aerobic metabolism in Svalbard permafrost
(Journal article; Peer reviewed, 2020)Permafrost underlies a large portion of the land in the Northern Hemisphere. It is proposed to be an extreme habitat and home for coldadaptive microbial communities. Upon thaw permafrost is predicted to exacerbate increasing ... 
Classification of quadratic APN functions with coefficients in F2 for dimensions up to 9
(Journal article; Peer reviewed, 2020)Almost perfect nonlinear (APN) and almost bent (AB) functions are integral components of modern block ciphers and play a fundamental role in symmetric cryptography. In this paper, we describe a procedure for searching for ... 
A New Family of APN Quadrinomials
(Journal article; Peer reviewed, 2020)The binomial B(x) = x 3 +βx 36 (where β is primitive in F 2 2) over F 2 10 is the first known example of an Almost Perfect Nonlinear (APN) function that is not CCZequivalent to a power function, and has remained unclassified ... 
Partially APN functions with APNlike polynomial representations
(Journal article; Peer reviewed, 2020)In this paper we investigate several families of monomial functions with APNlike exponents that are not APN, but are partially 0APN for infinitely many extensions of the binary field F2. We also investigate the differential ... 
Making the BKW Algorithm Practical for LWE
(Journal article; Peer reviewed, 2020)The Learning with Errors (LWE) problem is one of the main mathematical foundations of postquantum cryptography. One of the main groups of algorithms for solving LWE is the BlumKalaiWasserman (BKW) algorithm. This paper ...