Capturing the drunk robber on a graph (Q406701): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Peter M. Winkler / rank | |||
Property / author | |||
Property / author: Peter M. Winkler / rank | |||
Normal rank | |||
Property / review text | |||
Summary: We show that the expected time for a smart ``cop'' to catch a drunk ``robber'' on an \(n\)-vertex graph is at most \(n +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+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. | |||
Property / review text: Summary: We show that the expected time for a smart ``cop'' to catch a drunk ``robber'' on an \(n\)-vertex graph is at most \(n +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+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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C57 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C81 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 91A43 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 91A24 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6341631 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
random walks | |||
Property / zbMATH Keywords: random walks / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
pursuit games on graphs | |||
Property / zbMATH Keywords: pursuit games on graphs / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1305.4559 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Maximum hitting time for random walks on graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Gibbs measures and dismantlable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Collisions Among Random Walks on a Graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Projective Planes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Vertex-to-vertex pursuit in a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A probabilistic approach to Carne's bound / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Maximum diameter of regular digraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3706274 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Cumulative Sums of Random Variables / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the cop number of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The capture time of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On cop-win graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on \(k\)-cop, \(l\)-robber games on graphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:17, 9 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Capturing the drunk robber on a graph |
scientific article |
Statements
Capturing the drunk robber on a graph (English)
0 references
9 September 2014
0 references
Summary: We show that the expected time for a smart ``cop'' to catch a drunk ``robber'' on an \(n\)-vertex graph is at most \(n +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+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.
0 references
random walks
0 references
pursuit games on graphs
0 references