Now showing items 353-372 of 542

• #### 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 ...
• #### 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 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 Eulerian deletion problems ﻿

(Peer reviewed; Journal article, 2014-01)
We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the 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, 2012-09)
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 apex-minor-free graphs, a general class ...
• #### Parameterized Graph Modification Algorithms ﻿

(Doctoral thesis, 2015-12-10)
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 k-Clustering: Tractability Island ﻿

(Peer reviewed; Journal article, 2019)
In k-Clustering 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 Single-Exponential 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 minimum-weight tree that contains ...
• #### Parameterized streaming algorithms for min-ones d-SAT ﻿

(Journal article; Peer reviewed, 2019)
In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF 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, ...
• #### 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(UCS-RFID). The security of the UCSRFID relies on five dynamic secret keys which are updated at ...
• #### 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 F-Contraction ...
• #### Perceptually Uniform Motion Space ﻿

(Peer reviewed; Journal article, 2014-05-07)
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 ...