Browsing Department of Informatics by Title
Now showing items 610-629 of 917
-
Optimizing Approximate Weighted Matching on Nvidia Kepler K40
(Chapter; Peer reviewed, 2018)Matching is a fundamental graph problem with numerous applications in science and engineering. While algorithms for computing optimal matchings are difficult to parallelize, approximation algorithms on the other hand ... -
Order Reconfiguration Under Width Constraints
(Journal article; Peer reviewed, 2021)In this work, we consider the following order reconfiguration problem: Given a graph G together with linear orders ω and ω' of the vertices of G, can one transform ω into ω' by a sequence of swaps of adjacent elements in ... -
Order Reconfiguration under Width Constraints
(Journal article; Peer reviewed, 2023)In this work, we consider the following order reconfiguration problem: Given a graph G together with linear orders ω and ω′ of the vertices of G, can one transform ω into ω′ by a sequence of swaps of adjacent elements in ... -
Order-Related Problems Parameterized by Width
(Doctoral thesis, 2022-05-25)In the main body of this thesis, we study two different order theoretic problems. The first problem, called Completion of an Ordering, asks to extend a given finite partial order to a complete linear order while respecting ... -
ORFik: a comprehensive R toolkit for the analysis of translation
(Journal article; Peer reviewed, 2021)Background With the rapid growth in the use of high-throughput methods for characterizing translation and the continued expansion of multi-omics, there is a need for back-end functions and streamlined tools for processing, ... -
Ouroboros-E: An efficient Lattice-based Key-Exchange Protocol
(Peer reviewed; Journal article, 2018)The Bit Flipping algorithm is a hard decision decoding algorithm originally designed by Gallager in 1962 to decode Low Density Parity Check Codes (LDPC). It has recently proved to be much more versatile, for Moderate Parity ... -
Output-Sensitive Filtering of Streaming Volume Data
(Peer reviewed; Journal article, 2016-02)Real-time volume data acquisition poses substantial challenges for the traditional visualization pipeline where data enhancement is typically seen as a pre-processing step. In the case of 4D ultrasound data, for instance, ... -
P3 problem and Magnolia language: Specializing array computations for emerging architectures
(Journal article; Peer reviewed, 2022)The problem of producing portable high-performance computing (HPC) software that is cheap to develop and maintain is called the P3 (performance, portability, productivity) problem. Good solutions to the P3 problem have ... -
Packing arc-disjoint 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 ... -
Packing cycles faster than Erdos-Posa
(Journal article; Peer reviewed, 2019)The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since the publication of the classic Erdös--Pósa theorem in 1965, this problem received significant attention ... -
Parallel algorithms for computing k-connectivity
(Master thesis, 2017-05-05) -
Parallel algorithms for matching under preference
(Master thesis, 2017-06-20) -
Parallel Graph Algorithms for Combinatorial Scientific Computing
(Doctoral thesis, 2011-08-26) -
Parallel Matching and Clustering Algorithms on GPUs
(Doctoral thesis, 2017-06-17) -
Parameter optimisation for the improved modelling of industrial-scale gas explosions
(Doctoral thesis, 2019-06-17)This thesis presents work on improving the predictive capabilities of a numerical model by parameter optimisation. The numerical model is based on computational fluid dynamics (CFD) and predicts the consequences of ... -
Parameterization Above a Multiplicative Guarantee
(Journal article; Peer reviewed, 2020)Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given ... -
Parameterized complexity classification of deletion to list matrix-partition for low-order 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 M-partition of G with respect to L is a partition of V(G) into l parts, ... -
Parameterized complexity of categorical clustering with size constraints
(Journal article; Peer reviewed, 2023) -
Parameterized complexity of conflict-free matchings and paths
(Journal article; Peer reviewed, 2019)An input to a conflict-free variant of a classical problem Gamma, called Conflict-Free Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to Conflict-Free Gamma in (I,H) ... -
Parameterized Complexity of Directed Spanner Problems
(Journal article; Peer reviewed, 2020)We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance ...