9 papers
Text Indexing: From Reporting to Counting
Ben Bals, Panagiotis Charalampopoulos, Oded Lachish +2
We prove an elementary yet powerful combinatorial lemma: in any rooted tree with leaves, the number of nodes whose depth is smaller than the number of their leaf descendants is…
A characterization of one-sided error testable graph properties in bounded degeneracy graphs
Oded Lachish, Amit Levi, Ilan Newman +1
We consider graph property testing in -degenerate graphs under the random neighbor oracle model (Czumaj and Sohler, FOCS 2019). In this framework, a tester explores a graph by s…
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 $…
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…