Grants and Contributions:

Back to search

Title:

Combinatorial problems from the perspective of algorithms and complexity

Agreement Number:

RGPIN

Agreement Value:

$115,000.00

Agreement Date:

May 10, 2017 -

Organization:

Natural Sciences and Engineering Research Council of Canada

Location:

British Columbia, CA

Reference Number:

GC-2017-Q1-01999

Agreement Type:

Grant

Report Type:

Grants and Contributions

Additional Information:

Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023)

Recipient's Legal Name:

MacGillivray, Gary (University of Victoria)

Program:

Discovery Grants Program - Individual

Program Purpose:

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.