Grant: Discovery Grants Program - Individual
Dalhousie University
$28,000.00
Games and graphs
EF 2009-10
Résumé
Well-covered graphs: Divide-and-conquer is a well-tried and useful approach to hard problems. On the other hand, well-covered graphs have the property that hard problems (like scheduling jobs or examinations) are easy: the hard part is recognizing when a graph is well-covered. A labeling approach based on recognizing when two `jobs' cannot be scheduled at the same time partitions the graph into well-covered subgraphs that allows an easy but good starting point from which to schedule all the `jobs'.
`Decontaminating a network' can mean catching intruders to cleaning up chemical or biological contamination. Of particular interest for this proposal is the situation where the network has to be cleaned regularly because of a slow growing contaminant which may be anything from algae in the pipes of a power plant to dust in a house.
Combinatorial games are two person games of perfect information and without chance elements. The theory provides techniques for determining who can win from a game position and how. While ad hoc techniques for such analysis are as old as humanity, the modern theory employs more powerful and general tools such as the notion of a game-theoretic value and reduced canonical form. From a mathematical standpoint, these techniques can be brought to bear to completely solve a wide variety of games.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Nova Scotia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
4820-2009
Name nom
Nowakowski, Richard
Department département
Mathematics and Statistics
Organization id
79
Institution établissement
Dalhousie University
Province en
Nova Scotia
Province fr
Nouvelle-Écosse
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2009
Competition year année de concours
2009
Award amount
28000
Program id
RGPIN
Program nane 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
337
Committee name en
Pure & Applied Maths - B
Committee name fr
Maths pures et appliquées - B
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
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
1
Nb partie
5
Application title
Games and graphs
Keyword
NA
Application summary
Well-covered graphs: Divide-and-conquer is a well-tried and useful approach to hard problems. On the other hand, well-covered graphs have the property that hard problems (like scheduling jobs or examinations) are easy: the hard part is recognizing when a graph is well-covered. A labeling approach based on recognizing when two `jobs' cannot be scheduled at the same time partitions the graph into well-covered subgraphs that allows an easy but good starting point from which to schedule all the `jobs'.
`Decontaminating a network' can mean catching intruders to cleaning up chemical or biological contamination. Of particular interest for this proposal is the situation where the network has to be cleaned regularly because of a slow growing contaminant which may be anything from algae in the pipes of a power plant to dust in a house.
Combinatorial games are two person games of perfect information and without chance elements. The theory provides techniques for determining who can win from a game position and how. While ad hoc techniques for such analysis are as old as humanity, the modern theory employs more powerful and general tools such as the notion of a game-theoretic value and reduced canonical form. From a mathematical standpoint, these techniques can be brought to bear to completely solve a wide variety of games.