Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$31,000.00

Search Based Graph Algorithms

EF 2019-20

Résumé
A ""graph"", also called a ""network"" consists of a set of nodes together with a set of edges, each edge joining a particular pair of nodes. For example, consider a social network on students in a given class. Each student in the class is a node in the graph/network. The edges joining pairs of nodes could represent mutual friendship in which case the edges have no direction, or one directional friendship in which case the edges are directed. Given such a friendship network, we may wish to find ""cliques"" of friends, namely sets of nodes such that each person in the clique is a friend with everyone else in the clique. Designing an algorithm to find such a clique in a graph is a typical task for computer scientists - hopefully, such algorithms should be efficient and easy to implement.******One of the fundamental graph algorithmic paradigms is ""graph searching"" where the algorithm follows a prescribed method of visiting all vertices of the graph. Such search algorithms were developed in the late 1890s to solve maze problems. Recently it has been shown that many graph problems can be solved by using graph searching and new types of searches are currently being found. ******My research involves finding such graph searching based algorithms; often searching is used in a multi-sweep fashion where the output of one search serves as the input for the next search.**
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2016-05565
Name nom
Corneil, Derek
Department département
Computer Science (St. George Campus)
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2016
Award amount
31000
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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2714
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Mathematics of computing
Research subject fr
Mathématiques de l'informatique
Installment
inst:3 - 5
Partie
3
Nb partie
5
Application title
Search Based Graph Algorithms
Keyword
NSERC
Application summary
A ""graph"", also called a ""network"" consists of a set of nodes together with a set of edges, each edge joining a particular pair of nodes. For example, consider a social network on students in a given class. Each student in the class is a node in the graph/network. The edges joining pairs of nodes could represent mutual friendship in which case the edges have no direction, or one directional friendship in which case the edges are directed. Given such a friendship network, we may wish to find ""cliques"" of friends, namely sets of nodes such that each person in the clique is a friend with everyone else in the clique. Designing an algorithm to find such a clique in a graph is a typical task for computer scientists - hopefully, such algorithms should be efficient and easy to implement.******One of the fundamental graph algorithmic paradigms is ""graph searching"" where the algorithm follows a prescribed method of visiting all vertices of the graph. Such search algorithms were developed in the late 1890s to solve maze problems. Recently it has been shown that many graph problems can be solved by using graph searching and new types of searches are currently being found. ******My research involves finding such graph searching based algorithms; often searching is used in a multi-sweep fashion where the output of one search serves as the input for the next search.**