Grant: Discovery Grants Program - Individual
University of Victoria
$19,000.00
Combinatorial problems with a view towards algorithms and complexity
FY 2008-09
Summary
The proposed research involves the design of efficient algorithms, or a demonstration that no such algorithm is likely to exist, for certain combinatorial problems. As much of the research program as possible is to be carried out in such a way that opportunities are provided for undergraduate students, Master's students, Ph.D. students, post-doctoral fellows, and young colleagues. There are three main topics involved: homomorphisms of graphs, discrete-time graph processes, and domination in graphs. The first of these has applications in computer science, scheduling, and logic. The second topic involves, among other things, a very simple yet computational difficult model of the spread of a virus or disease through a network or population. The final topic is arguably among the most well-studied in discrete mathematics and theoretical computer science. Besides being interesting for its own sake, it has proved to be an excellent vehicle for involving students in research.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
137763-2007
Name nom
MacGillivray, Gary
Department département
Mathematics and Statistics
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2007
Award amount
19000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2703
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Complexity
Research subject fr
Complexité
Partie
2
Nb partie
5
Application title
Combinatorial problems with a view towards algorithms and complexity
Keyword
NA
Application summary
The proposed research involves the design of efficient algorithms, or a demonstration that no such algorithm is likely to exist, for certain combinatorial problems. As much of the research program as possible is to be carried out in such a way that opportunities are provided for undergraduate students, Master's students, Ph.D. students, post-doctoral fellows, and young colleagues. There are three main topics involved: homomorphisms of graphs, discrete-time graph processes, and domination in graphs. The first of these has applications in computer science, scheduling, and logic. The second topic involves, among other things, a very simple yet computational difficult model of the spread of a virus or disease through a network or population. The final topic is arguably among the most well-studied in discrete mathematics and theoretical computer science. Besides being interesting for its own sake, it has proved to be an excellent vehicle for involving students in research.