Browsing Department of Informatics by Title
Now showing items 433452 of 643

Parameterized complexity of PCA
(Journal article; Peer reviewed, 2020)We discuss some recent progress in the study of Principal Component Analysis (PCA) from the perspective of Parameterized Complexity. 
Parameterized complexity of secluded connectivity problems
(Conference object; Peer reviewed; Journal article, 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 ... 
Parameterized complexity of the spanning tree congestion problem
(Peer reviewed; Journal article, 201209)We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apexminorfree graphs, a general class ... 
Parameterized Graph Modification Algorithms
(Doctoral thesis, 20151210)Graph modification problems form an important class of algorithmic problems in computer science. In this thesis, we study edge modification problems towards classes related to chordal graphs, with the main focus on trivially ... 
Parameterized kClustering: Tractability Island
(Peer reviewed; Journal article, 2019)In kClustering we are given a multiset of n vectors X subset Z^d and a nonnegative number D, and we need to decide whether X can be partitioned into k clusters C_1, ..., C_k such that the cost sum_{i=1}^k min_{c_i in R^d} ... 
Parameterized SingleExponential Time Polynomial Space Algorithm for Steiner Tree
(Peer reviewed; Journal article, 2019)In the Steiner Tree problem, we are given as input a connected \(n\)vertex graph with edge weights in \(\{1,2,\ldots,W\}\), and a set of \(k\) terminal vertices. Our task is to compute a minimumweight tree that contains ... 
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 ... 
Parsing in a Broad Sense
(Lecture Notes in Computer Science: 8767, Chapter; Peer reviewed, 2014)Having multiple representations of the same instance is common in software language engineering: models can be visualised as graphs, edited as text, serialised as XML. When mappings between such representations are considered, ... 
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 ... 
Partitioning a graph into degenerate subgraphs
(Journal article; Peer reviewed, 202001)Let G = (V, E) be a connected graph with maximum degree k ≥ 3 distinct from Kk+1. Given integers s ≥ 2 and p1, . . . , ps ≥ 0, G is said to be (p1, . . . , ps)partitionable if there exists a partition of V into sets ... 
Passive Cryptanalysis of the UnConditionally Secure Authentication Protocol for RFID Systems
(Conference object, 2012)Recently, Alomair et al. proposed the first Un Conditionally Secure mutual authentication protocol for lowcost RFID systems(UCSRFID). The security of the UCSRFID relies on five dynamic secret keys which are updated at ... 
Path contraction faster than $2^n$
(Journal article; Peer reviewed, 2020)A graph $G$ is contractible to a graph $H$ if there is a set $X \subseteq E(G)$, such that $G/X$ is isomorphic to $H$. Here, $G/X$ is the graph obtained from $G$ by contracting all the edges in $X$. For a family of graphs ... 
Path Contraction Faster Than 2n
(Peer reviewed; Journal article, 2019)A graph G is contractible to a graph H if there is a set X subseteq E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs F, the FContraction ... 
Perceptually Uniform Motion Space
(Peer reviewed; Journal article, 20140507)Flow data is often visualized by animated particles inserted into a flow field. The velocity of a particle on the screen is typically linearly scaled by the velocities in the data. However, the perception of velocity ... 
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, ... 
Pharmacokinetics and transcriptional effects of the antisalmon lice drug emamectin benzoate in Atlantic salmon (Salmo salar L.)
(Peer reviewed; Journal article, 20080911)Background: Emamectin benzoate (EB) is a dominating pharmaceutical drug used for the treatment and control of infections by sea lice (Lepeophtheirus salmonis) on Atlantic salmon (Salmo salar L). Fish with an initial mean ... 
Phase Transition in a System of Random Sparse Boolean Equations
(Chapter; Peer reviewed, 2012)Many problems, including algebraic cryptanalysis, can be transformed to a problem of solving a (large) system of sparse Boolean equations. In this article we study 2 algorithms that can be used to remove some redundancy ... 
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 ... 
A Polynomial Kernel for PawFree Editing
(Journal article; Peer reviewed, 2020)For a fixed graph H, the Hfree Edge Editing problem asks whether we can modify a given graph G by adding or deleting at most k edges such that the resulting graph does not contain H as an induced subgraph. The problem is ... 
A polynomialtime algorithm for LO based on generalized logarithmic barrier functions
(Peer reviewed; Journal article, 2008)