Grant: Discovery Grants Program - Individual
University of Saskatchewan
$23,000.00
Combinatorics of Mixed Graphs -- Complexity and Homomorphism
EF 2019-20
Résumé
Graph models are a fundamental tool for those working with relational data; they allow social scientists to study changing social and political alliances within a social network; they allow medical schools and hospitals a method to fairly pair medical residents with hospitals; and they allow engineers to find efficient schedules for large-scale engineering projects. However, these models are limited in that they often assume that the relationship between a pair of objects (such as people, resident and hospitals, or tasks) is identical, regardless of the pair being considered. ******In this research we study a graph model that allows for a more sophisticated notion of relationship. For example, using such a model, researchers can study social networks in which the relationship between family members is noted as a different kind of relationship as that between friends. The long-term goal of this research is to develop tools for graph models with this more sophisticated notion of relationship so that researchers and industry may apply these models in their respective areas. In particular, this research focusses on assignment problems; problems in which objects are grouped, or not grouped, based on their relationship to one another. The past study of assignment problems has lead to improvements in compiler use in parallel processing, in frequency assignments in radio communications networks, and in timetable scheduling. This research explores fundamental questions about the computational nature of assignment problems defined for graph models with more sophisticated notions of relationship. It characterizes these problems based on the existence (or suspected lack thereof) of efficient algorithms. For those problems for which it is expected that no efficient algorithm can exist, this research develops approximation algorithms, algorithms that provide a solution that is guaranteed to approximate the optimal solution within a fixed error bound.**
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Saskatchewan, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2019-04857
Name nom
Duffy, Christopher
Department département
Mathematics and Statistics
Organization id
16
Institution établissement
University of Saskatchewan
Province en
Saskatchewan
Province fr
Saskatchewan
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2019
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
Technologie de l'information
Research subject en
Complexity
Research subject fr
Complexité
Installment
inst:1 - 5
Partie
1
Nb partie
5
Application title
Combinatorics of Mixed Graphs -- Complexity and Homomorphism
Keyword
NSERC
Application summary
Graph models are a fundamental tool for those working with relational data; they allow social scientists to study changing social and political alliances within a social network; they allow medical schools and hospitals a method to fairly pair medical residents with hospitals; and they allow engineers to find efficient schedules for large-scale engineering projects. However, these models are limited in that they often assume that the relationship between a pair of objects (such as people, resident and hospitals, or tasks) is identical, regardless of the pair being considered. ******In this research we study a graph model that allows for a more sophisticated notion of relationship. For example, using such a model, researchers can study social networks in which the relationship between family members is noted as a different kind of relationship as that between friends. The long-term goal of this research is to develop tools for graph models with this more sophisticated notion of relationship so that researchers and industry may apply these models in their respective areas. In particular, this research focusses on assignment problems; problems in which objects are grouped, or not grouped, based on their relationship to one another. The past study of assignment problems has lead to improvements in compiler use in parallel processing, in frequency assignments in radio communications networks, and in timetable scheduling. This research explores fundamental questions about the computational nature of assignment problems defined for graph models with more sophisticated notions of relationship. It characterizes these problems based on the existence (or suspected lack thereof) of efficient algorithms. For those problems for which it is expected that no efficient algorithm can exist, this research develops approximation algorithms, algorithms that provide a solution that is guaranteed to approximate the optimal solution within a fixed error bound.**