 |
RUTCOR Colloquia - April 5, 2007
Speaker: Dimitrios M. Thilikos
Affiliation: Department of Mathematics, National and Capodistrian University of Athens, Athens, Greece.
Title: Graph Searching in a Crime Wave.
Time: 1:30 - 2:30 PM
Location: RUTCOR Building - Room 139, Rutgers University, Busch Campus, Piscataway, NJ
Abstracts:
We define helicopter cop and robber games with multiple robbers, extending
previous research, which only considered the pursuit
of a single robber. Our model is defined for robbers that are visible
(their position in the graph is known to the cops) and active (able to
move at any point in the game) but is easily adapted to other
variants of the game that have been considered in the literature. We
show that the game with many robbers is non-monotone: that is, fewer
cops are needed if the robbers are allowed to reoccupy positions that
were previously unavailable to them because of the cops' position. As
the moves of the cops depend on the position of the visible robbers,
strategies for such games should be interactive but
the game becomes, in a sense, less interactive as the initial number
of robbers increases. We prove that the main parameter emerging from
the game, which we denote ${\bf mvams}(G,r)$, captures a hierarchy of
parameters between proper pathwidth and proper treewidth and we
completely characterize it for trees, extending analogous existing
characterizations of the pathwidth of trees. Moreover, we prove an
upper bound for ${\bf mvams}(G,r)$ on general graphs. However, if we
consider the robbers to be invisible and lazy, the resulting
parameters collapse in all cases to either pathwidth or treewidth,
giving a further case where the classic equivalence between visible,
active robbers and invisible, lazy robbers does not hold.
Back to Seminars Page.
Back to RUTCOR homepage.
|
