Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Université de Montréal

$17,000.00

Graph searching and applications

FY 2015-16

Summary
Cops-and-robbers games are useful in modelling various graph widths, which in turn are useful in the design of efficient algorithms. They are also useful in robotics by modelling different problems that robots used in practical situation may encounter. This proposal is concerned with the mathematics of the latter applications. In this case, a cop and a robber play on a given graph, by alternating moves from a vertex to one of its neighbours, until the cop occupies the same vertex as the robber. Thus a robot can attempt to locate an intruder in a network or in a maze. In particular, we investigate, for graphs on which the cop has a winning strategy, the length of games in which each player moves intelligently, that is, the cop tries to catch the robber as fast as possible while the robber tries to survive as long as possible. We also consider a new and more general game, in which a number of cops play on one graph G, trying to capture a number of robbers on another graph H. The capture relation between G and H governs the game. This can model, for example, a robot moving in one room, while his position is translated to a situation elsewhere (a discrete version of a mouse on a pad one uses with a computer, except of course the robot is not controlled by a human). As an extension, we look at the games on infinite graphs since their gaming properties are quite different. While this is a purely mathematical endeavour, some of the results could be applicable to the web graph as some people like to model it by an in infinite one. Note that the numerous people that work on graph searching are ready for industrial collaboration.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
199-2012
Name nom
Hahn, Gena
Department département
Informatique et recherche opérationnelle
Organization id
63
Institution établissement
Université de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2012
Award amount
17000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2714
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Mathematics of computing
Research subject fr
Mathématiques de l'informatique
Partie
4
Nb partie
5
Application title
Graph searching and applications
Keyword
NSERC
Application summary
Cops-and-robbers games are useful in modelling various graph widths, which in turn are useful in the design of efficient algorithms. They are also useful in robotics by modelling different problems that robots used in practical situation may encounter. This proposal is concerned with the mathematics of the latter applications. In this case, a cop and a robber play on a given graph, by alternating moves from a vertex to one of its neighbours, until the cop occupies the same vertex as the robber. Thus a robot can attempt to locate an intruder in a network or in a maze. In particular, we investigate, for graphs on which the cop has a winning strategy, the length of games in which each player moves intelligently, that is, the cop tries to catch the robber as fast as possible while the robber tries to survive as long as possible. We also consider a new and more general game, in which a number of cops play on one graph G, trying to capture a number of robbers on another graph H. The capture relation between G and H governs the game. This can model, for example, a robot moving in one room, while his position is translated to a situation elsewhere (a discrete version of a mouse on a pad one uses with a computer, except of course the robot is not controlled by a human). As an extension, we look at the games on infinite graphs since their gaming properties are quite different. While this is a purely mathematical endeavour, some of the results could be applicable to the web graph as some people like to model it by an in infinite one. Note that the numerous people that work on graph searching are ready for industrial collaboration.