5 citations · 9 across the 14 of their papers we have counts for
7 papers · 1 filter
A practical algorithm for 3-admissibility
Christine Awofeso, Patrick Greaves, Oded Lachish +1
The -admissibility of a graph is a promising measure to identify real-world networks that have an algorithmically favourable structure. We design an algorithm that decides wheth…
Efficient Trace Frequency Queries in Sparse Graphs
Christine Awofeso, Pål Grønås Drange, Patrick Greaves +2
Understanding how a vertex relates to a set of vertices is a fundamental task in graph analysis. Given a graph and a vertex set , consider the collection of s…
A sufficient condition for characterizing the one-sided testable properties of families of graphs in the Random Neighbour Oracle Model
Christine Awofeso, Patrick Greaves, Oded Lachish +2
We study property testing in the \emph{random neighbor oracle} model for graphs, originally introduced by Czumaj and Sohler [STOC 2019]. Specifically, we initiate the study of char…
Counting large patterns in degenerate graphs
Christine Awofeso, Patrick Greaves, Oded Lachish +1
The problem of subgraph counting asks for the number of occurrences of a pattern graph as a subgraph of a host graph and is known to be computationally challenging: it is $…
Testing Quasiperiodicity
Christine Awofeso, Ben Bals, Oded Lachish +1
A cover (or quasiperiod) of a string is a shorter string such that every position of is contained in some occurrence of as a substring. The notion of covers was int…
A practical algorithm for 2-admissibility
Christine Awofeso, Patrick Greaves, Oded Lachish +1
The -admissibility of a graph is a promising measure to identify real-world networks which have an algorithmically favourable structure. In contrast to other related measures, l…