27 citations · 100 across the 27 of their papers we have counts for
42 papers
The parameterised complexity of generalised temporal domination on temporal graphs with modular structure
Jessica Enright, Kitty Meeks, Elena Moss
Inspired by the static problem -Dominating Set, we propose a general temporal domination problem, called -Temporal Dominating Set (-TDS). We show that this pro…
Temporal Role Colouring
Jessica Enright, Kitty Meeks, Puck Rombach +1
A role colouring of a graph is an assignment of colours to the vertices of such that two vertices of the same colour have identical sets of colours in their neighbourhoods.…
The Parameterised Complexity of Temporal Motif Counting, and a Lovász-Style Isomorphism Theorem
Jayakrishnan Madathil, Kitty Meeks, Marc Roth
We study the structural expressivity and the parameterised complexity of counting homomorphisms from small temporal patterns to large temporal graphs. Here, a temporal pattern …
Approximating temporal modularity on graphs of small underlying treewidth
Vilhelm Agdur, Jessica Enright, Laura Larios-Jones +3
Modularity is a very widely used measure of the level of clustering or community structure in networks. Here we consider a recent generalisation of the definition of modularity to…
Temporal Orienteering with Changing Fuel Costs
Timothée Corsini, Jessica Enright, Laura Larios-Jones +1
The problem Orienteering asks whether there exists a walk which visits a number of sites without exceeding some fuel budget. In the variant of the problem we consider, the cost of…
Families of tractable problems with respect to vertex-interval-membership width and its generalisations
Jessica Enright, Samuel D. Hand, Laura Larios-Jones +1
Temporal graphs are graphs whose edges are labelled with times at which they are active. Their time-sensitivity provides a useful model of real networks, but renders many problems…
Temporal Triadic Closure: Finding Dense Structures in Social Networks That Evolve
Tom Davot, Jessica Enright, Jayakrishnan Madathil +1
A graph G is c-closed if every two vertices with at least c common neighbors are adjacent to each other. Introduced by Fox, Roughgarden, Seshadhri, Wei and Wein [ICALP 2018, SICOMP…
Reachability in temporal graphs under perturbation
Jessica Enright, Laura Larios-Jones, Kitty Meeks +1
Reachability and other path-based measures on temporal graphs can be used to understand spread of infection, information, and people in modelled systems. Due to delays and errors i…
Structural Parameters for Dense Temporal Graphs
Jessica Enright, Samuel D. Hand, Laura Larios-Jones +1
Temporal graphs provide a useful model for many real-world networks. Unfortunately the majority of algorithmic problems we might consider on such graphs are intractable. There has…
Parameterized Algorithms for Balanced Cluster Edge Modification Problems
Jayakrishnan Madathil, Kitty Meeks
We study {\sc Cluster Edge Modification} problems with constraints on the size of the clusters. A graph is a cluster graph if every connected component of is a clique. In a…
Cops and Robbers on Multi-Layer Graphs
Jessica Enright, Kitty Meeks, William Pettersson +1
We generalise the popular cops and robbers game to multi-layer graphs, where each cop and the robber are restricted to a single layer (or set of edges). We show that initial intuit…
Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
Holger Dell, John Lapinskas, Kitty Meeks
We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle q…
Counting Subgraphs in Somewhere Dense Graphs
Marco Bressan, Leslie Ann Goldberg, Kitty Meeks +1
We study the problems of counting copies and induced copies of a small pattern graph in a large host graph . Recent work fully classified the complexity of those problems ac…
Making Life More Confusing for Firefighters
Samuel Hand, Jessica Enright, Kitty Meeks
It is well known that fighting a fire is a hard task. The Firefighter problem asks how to optimally deploy firefighters to defend the vertices of a graph from a fire. This problem…
Counting Temporal Paths
Jessica Enright, Kitty Meeks, Hendrik Molter
The betweenness centrality of a vertex v is an important centrality measure that quantifies how many optimal paths between pairs of other vertices visit v. Computing betweenness ce…
A New Temporal Interpretation of Cluster Editing
Cristiano Bocci, Chiara Capresi, Kitty Meeks +1
The NP-complete graph problem Cluster Editing seeks to transform a static graph into a disjoint union of cliques by making the fewest possible edits to the edges. We introduce a na…
Tangled Paths: A Random Graph Model from Mallows Permutations
Jessica Enright, Kitty Meeks, William Pettersson +1
We introduce the random graph which results from taking the union of two paths of length , where the vertices of one of the paths have been relabelled a…
Edge exploration of temporal graphs
Benjamin Merlin Bumpus, Kitty Meeks
We introduce a natural temporal analogue of Eulerian circuits and prove that, in contrast with the static case, it is NP-hard to determine whether a given temporal graph is tempora…
Reconstructing the degree sequence of a sparse graph from a partial deck
Carla Groenland, Tom Johnston, Andrey Kupavskii +3
The deck of a graph is the multiset of cards . Myrvold (1992) showed that the degree sequence of a graph on vertices can be reconstructed from any d…
Improved inference for areal unit count data using graph-based optimisation
Duncan Lee, Kitty Meeks
Spatial correlation in areal unit count data is typically modelled by a set of random effects that are assigned a conditional autoregressive (CAR) prior distribution. The spatial c…
The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
Jessica Enright, Duncan Lee, Kitty Meeks +2
Understanding spatial correlation is vital in many fields including epidemiology and social science. Lee, Meeks and Pettersson (Stat. Comput. 2021) recently demonstrated that impro…
Directed branch-width: A directed analogue of tree-width
Benjamin Merlin Bumpus, Kitty Meeks, William Pettersson
Gurski and Wanke showed that a graph class C has bounded tree-width if and only if its associated class of directed line graphs has bounded clique-width. Inevitably -- asking wheth…
Approximately counting and sampling small witnesses using a colourful decision oracle
Holger Dell, John Lapinskas, Kitty Meeks
In this paper, we design efficient algorithms to approximately count the number of edges of a given -hypergraph, and to sample an approximately uniform random edge. The hypergra…
The parameterised complexity of computing the maximum modularity of a graph
Kitty Meeks, Fiona Skerman
The maximum modularity of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph…