Patrick Greaves

dblp:355/0256 · DBLP profile ↗
← Back
7ranked-venue papers
0as first author
7since 2021 · last 2026
0009-0007-0752-0526ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 4 · 4 since 2021Applied, interdisciplinary, general and emerging computing · 3 · 3 since 2021
YearPublicationVenuePosition
2026 Efficient Trace Frequency Queries in Sparse Graphs
Christine Awofeso, Pål Grønås Drange, Patrick Greaves, Oded Lachish, Felix Reidl
SOFSEM3
2026 A Practical Algorithm for 3-Admissibility
Christine Awofeso, Patrick Greaves, Oded Lachish, Felix Reidl
SOFSEM2
2026 Counting Large Patterns in Degenerate Graphs
Christine Awofeso, Patrick Greaves, Oded Lachish, Felix Reidl
SOFSEM2
2025 Testing C_k-Freeness in Bounded Admissibility Graphs
Christine Awofeso, Patrick Greaves, Oded Lachish, Amit Levi 0001, Felix Reidl
ICALP2
2025 Results on H-Freeness Testing in Graphs of Bounded r-Admissibility
Christine Awofeso, Patrick Greaves, Oded Lachish, Felix Reidl
STACS2
2025 A Practical Algorithm for 2-Admissibility
abstract
The 2-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, like the weak/strong 2-colouring numbers or the maximum density of graphs that appear as 1-subdivisions, the 2-admissibility can be computed in polynomial time. However, so far these results are theoretical only and no practical implementation to compute the 2-admissibility exists. Here we present an algorithm which decides whether the 2-admissibility of an input graph G is at most p in time O(p⁴ |V(G)|) and space O(|E(G)| + p²). The simple structure of the algorithm makes it easy to implement. We evaluate our implementation on a corpus of 214 real-world networks and find that the algorithm runs efficiently even on networks with millions of edges, that it has a low memory footprint, and that indeed many networks have a small 2-admissibility.
Christine Awofeso, Patrick Greaves, Oded Lachish, Felix Reidl
SEA2
2023 Computing Complexity Measures of Degenerate Graphs
Pål Grønås Drange, Patrick Greaves, Irene Muzi, Felix Reidl
IPEC2