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 H-Graphs
(Journal article; Peer reviewed, 2020)For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. H-graphs naturally generalize several important graph classes like interval graphs or circular-arc ... -
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 next-generation sequencing for germline and somatic variants
(Journal article; Peer reviewed, 2020)Next-generation 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 Bit-Vector Differential Model for the Modular Addition by a Constant
(Journal article; Peer reviewed, 2020)ARX algorithms are a class of symmetric-key algorithms constructed by Addition, Rotation, and XOR, which achieve the best software performances in low-end microcontrollers. To evaluate the resistance of an ARX cipher against ... -
Transversals of longest paths
(Journal article; Peer reviewed, 2020-03)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 meta-transcriptomic data
(Journal article; Peer reviewed, 2020-03-13)Motivation Technological advances in meta-transcriptomics have enabled a deeper understanding of the structure and function of microbial communities. ‘Total RNA’ meta-transcriptomics, sequencing of total reverse transcribed ... -
Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
(Journal article; Peer reviewed, 2020)Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its ... -
A complexity dichotomy for critical values of the b-chromatic number of graphs
(Journal article; Peer reviewed, 2020)A b-coloring 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 b-Coloring 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, 2021-06-10)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 ... -
Metagenome-assembled 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 cold-adaptive 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 CCZ-equivalent to a power function, and has remained unclassified ... -
Partially APN functions with APN-like polynomial representations
(Journal article; Peer reviewed, 2020)In this paper we investigate several families of monomial functions with APN-like exponents that are not APN, but are partially 0-APN 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 post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum-Kalai-Wasserman (BKW) algorithm. This paper ...
RSS 2.0