31 citations · 62 across the 15 of their papers we have counts for
3 papers · 1 filter
Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
Holger Dell, John Lapinskas, Kitty Meeks
We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle q…
A Fixed-Parameter Perspective on #BIS
Radu Curticapean, Holger Dell, Fedor Fomin +2
The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexi…
Approximately counting locally-optimal structures
Leslie Ann Goldberg, Rob Gysel, John Lapinskas
A locally-optimal structure is a combinatorial structure such as a maximal independent set that cannot be improved by certain (greedy) local moves, even though it may not be global…