23 citations · 87 across the 20 of their papers we have counts for
6 papers · 1 filter
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…
When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument
Johannes Lengler, Anders Martinsson, Angelika Steger
Hillclimbing is an essential part of any optimization algorithm. An important benchmark for hillclimbing algorithms on pseudo-Boolean functions are (s…
Asymptotically Optimal Amplifiers for the Moran Process
Leslie Ann Goldberg, John Lapinskas, Johannes Lengler +3
We study the Moran process as adapted by Lieberman, Hauert and Nowak. This is a model of an evolving population on a graph or digraph where certain individuals, called "mutants" ha…
Bootstrap percolation on geometric inhomogeneous random graphs
Christoph Koch, Johannes Lengler
Geometric inhomogeneous random graphs (GIRGs) are a model for scale-free networks with underlying geometry. We study bootstrap percolation on these graphs, which is a process model…
Connectivity Thresholds for Bounded Size Rules
Hafsteinn Einarsson, Johannes Lengler, Konstantinos Panagiotou +2
In an Achlioptas process, starting with a graph that has n vertices and no edge, in each round edges are drawn uniformly at random, and using some rule exactly one of th…
Bootstrap percolation with inhibition
Hafsteinn Einarsson, Johannes Lengler, Konstantinos Panagiotou +2
Bootstrap percolation is a prominent framework for studying the spreading of activity on a graph. We begin with an initial set of active vertices. The process then proceeds in roun…