4 papers
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…
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…