Source author record

Natasha Komarov

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.PR

Catalog footprint

Research overview

3works

3topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Hunter & Mole

We consider a variation of a cops and robbers game in which the cop---here referred to as "hunter"---is not constrained by the graph but must play in the dark against a "mole." We characterize the graphs---which we will call "hunter-win"---on which the hunter can guarantee capture of the mole in bounded time. We also define an optimal hunter strategy (and consequently an upper bound on maximum game time on hunter-win graphs) and note that an optimal hunter strategy need not take advantage of the hunter's unconstrained movement! This game comes from a puzzle of unknown origin which was told to the authors by Dick Hess.

preprint2013arXiv

Capturing the Drunk Robber on a Graph

We show that the expected time for a smart "cop" to catch a drunk "robber" on an $n$ -vertex graph is at most $n + {\rm o}(n)$ . More precisely, let $G$ be a simple, connected, undirected graph with distinguished points $u$ and $v$ among its $n$ vertices. A cop begins at $u$ and a robber at $v$ ; they move alternately from vertex to adjacent vertex. The robber moves randomly, according to a simple random walk on $G$ ; the cop sees all and moves as she wishes, with the object of "capturing" the robber---that is, occupying the same vertex---in least expected time. We show that the cop succeeds in expected time no more than $n + {\rm o}(n)$ . Since there are graphs in which capture time is at least $n - o(n)$ , this is roughly best possible. We note also that no function of the diameter can be a bound on capture time.

preprint2013arXiv

Cops vs. Gambler

We consider a variation of cop vs.\ robber on graph in which the robber is not restricted by the graph edges; instead, he picks a time-independent probability distribution on $V(G)$ and moves according to this fixed distribution. The cop moves from vertex to adjacent vertex with the goal of minimizing expected capture time. Players move simultaneously. We show that when the gambler's distribution is known, the expected capture time (with best play) on any connected $n$ -vertex graph is exactly $n$ . We also give bounds on the (generally greater) expected capture time when the gambler's distribution is unknown to the cop.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.