Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Guelph

$19,000.00

Fast combinatorial and graph algorithms

EF 2011-12

Résumé
Suppose you are given a bag containing blue and yellow beads and are asked the following questions: How many different necklaces can you make with exactly 5 blue beads and 5 yellow beads? For this problem observe that the necklace ""bbbbbyyyyy"" is the same as ""bbyyyyybbb"" when the beads are rotated by 3 positions. Thus, when you attempt to produce a list of such necklaces, it is not a trivial task to ensure that there are no duplicates. This is an example of a problem encounted in the field of ""Combinatorial Generation"" which is a branch of theoretical computer science. In this area, the primary research goal is to develop fast computer algorithms to automatically produce exhaustive lists of fundamental mathematical objects - with no duplication. These objects, such as permutations, combinations, necklaces, and vertex orderings of graphs are often used to model important scientific problems. As an example, one of the most famous of such algorithms is the Binary Reflected Gray Code. This algorithm lists all binary numbers of length N so that each successive bit-string differs by exactly one bit from the previous bit-string. This algorithm was patented and used in pulse code communications. The primary goal of my research is to continue to develop efficient algorithms to produce exhaustive lists for specific objects. When developing such algorithms, intense study of each object is required, and this often leads to new insights about the object itself. The algorithms also enhance a toolbox of results that will be crucial for future researchers.
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
298335-2007
Name nom
Sawada, Joe
Department département
Computing and Information Science, School of
Organization id
24
Institution établissement
University of Guelph
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
5
Nb partie
5
Application title
Fast combinatorial and graph algorithms
Keyword
NSERC
Application summary
Suppose you are given a bag containing blue and yellow beads and are asked the following questions: How many different necklaces can you make with exactly 5 blue beads and 5 yellow beads? For this problem observe that the necklace ""bbbbbyyyyy"" is the same as ""bbyyyyybbb"" when the beads are rotated by 3 positions. Thus, when you attempt to produce a list of such necklaces, it is not a trivial task to ensure that there are no duplicates. This is an example of a problem encounted in the field of ""Combinatorial Generation"" which is a branch of theoretical computer science. In this area, the primary research goal is to develop fast computer algorithms to automatically produce exhaustive lists of fundamental mathematical objects - with no duplication. These objects, such as permutations, combinations, necklaces, and vertex orderings of graphs are often used to model important scientific problems. As an example, one of the most famous of such algorithms is the Binary Reflected Gray Code. This algorithm lists all binary numbers of length N so that each successive bit-string differs by exactly one bit from the previous bit-string. This algorithm was patented and used in pulse code communications. The primary goal of my research is to continue to develop efficient algorithms to produce exhaustive lists for specific objects. When developing such algorithms, intense study of each object is required, and this often leads to new insights about the object itself. The algorithms also enhance a toolbox of results that will be crucial for future researchers.