Grant: Discovery Grants Program - Individual
University of Victoria
$23,000.00
Combinatorial problems from the perspective of algorithms and complexity
EF 2023-24
Résumé
We propose a continuation of our long-term research program involving the study of graph colourings and homomorphisms, which have applications in scheduling and logistics, dominating sets, which have applications in locating resources and networks, and discrete-time graph processes, which have applications ranging from network security to automated cleaning of networks of pipes. An important feature of the study proposed is that as much of it as possible is to be carried out in such a way that development opportunities for undergraduate students, graduate students, post-doctoral fellows and young researchers are generated. A common feature to all of the topics we propose to study is time. We are looking for either computationally efficient solutions to the problems in question (solvable by a computer in a reasonable amount of time), or a demonstration that no such solution is likely to exist. When the latter situation arises, we look for approximate solutions that can be found efficiently or special cases of the problem that admit such solutions.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2017-04459
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
2023
Competition year année de concours
2017
Award amount
23000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
2703
Research subject group en
Information technology
Research subject group fr
Complexity
Research subject en
Technologie de l'information
Research subject fr
Complexité
Application title
Combinatorial problems from the perspective of algorithms and complexity
Keyword
Algorithms; Complexity; Discrete-time dynamic graph processes and games; Dominating sets; Graph colourings and homomorphisms; Reconfiguration problems
Application summary
We propose a continuation of our long-term research program involving the study of graph colourings and homomorphisms, which have applications in scheduling and logistics, dominating sets, which have applications in locating resources and networks, and discrete-time graph processes, which have applications ranging from network security to automated cleaning of networks of pipes. An important feature of the study proposed is that as much of it as possible is to be carried out in such a way that development opportunities for undergraduate students, graduate students, post-doctoral fellows and young researchers are generated. A common feature to all of the topics we propose to study is time. We are looking for either computationally efficient solutions to the problems in question (solvable by a computer in a reasonable amount of time), or a demonstration that no such solution is likely to exist. When the latter situation arises, we look for approximate solutions that can be found efficiently or special cases of the problem that admit such solutions.