Pawel Pralat
Some remarks on cops and drunk robbers.
Tue, 06/14/2011 - 15:01 — SomNambulAuthors: Pawel Pralat, Athanasios Kehagias
Subjects: Discrete Mathematics
AbstractThe cops and robbers game has been extensively studied under the assumption
of optimal play by both the cops and the robbers. In this paper we study the
problem in which cops are chasing a drunk robber (that is, a robber who
performs a random walk) on a graph. Our main goal is to characterize the "cost
of drunkenness." Specif?ically, we study the ratio of expected capture times
for the optimal version and the drunk robber one. We also examine the
algorithmic side of the problem; that is, how to compute near-optimal search
schedules for the cops.Rank-based attachment leads to power law graphs.
Tue, 08/25/2009 - 22:41 — SomNambulAuthors: Jeannette Janssen, Pawel Pralat
Subjects: Combinatorics
AbstractWe investigate the degree distribution resulting from graph generation models
based on rank-based attachment. In rank-based attachment, all vertices are
ranked according to a ranking scheme. The link probability of a given vertex is
proportional to its rank raised to the power -a, for some a in (0,1). Through a
rigorous analysis, we show that rank-based attachment models lead to graphs
with a power law degree distribution with exponent 1+1/a whenever vertices are
ranked according to their degree, their age, or a randomly chosen fitness
value.
User login
