31 citations · 62 across the 15 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
cs.DS2020
Faster Exponential-time Algorithms for Approximately Counting Independent Sets
Leslie Ann Goldberg, John Lapinskas, David Richerby
Counting the independent sets of a graph is a classical #P-complete problem, even in the bipartite case. We give an exponential-time approximation scheme for this problem which is…
math.PR2020★ 2 cited
Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs
Júlia Komjáthy, John Lapinskas, Johannes Lengler
We study the spread of information in finite and infinite inhomogeneous spatial random graphs. We assume that each edge has a transmission cost that is a product of an i.i.d. rando…