9 papers
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 …
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…
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…
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, Timothée Corsini, Jessica Enright +2
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…