Grant: Discovery Grants Program - Individual
University of Toronto
$62,000.00
Algorithmic graph theory
EF 2006-07
Résumé
A graph is a mathematical object consisting of a set of nodes together with a set of edges, each joining a pair of nodes. Graphs can be used to model many different types of networks, for example Protein-Protein Interaction (PPI) networks (the nodes are proteins and an edge between two proteins indicates that the proteins interact). The first job of a graph theorist is to determine the type of graph that occurs in practical instances of the application. In the case of PPI networks, we have recently shown that the model that most closely captures the currently available biological information is geometric random graphs, not scale-free graphs as presently accepted. Once a good model has been identified, the next step is to design fast, easily implementable algorithms to solve various problems on the particular model. Such algorithms often have to work on huge data sets, as anticipated for PPI networks. My research includes the study of restricted families of graphs that arise in practice and to design fast practical algorithms. One of the fundamental algorithmic notions in graph theory is searching, i.e. following a particular algorithm to visit all nodes and edges of the graph. Many graph algorithms include some aspect of graph searching, and we've recently determined that many other problems can be solved most efficiently using multi-sweep search algorithms. Our work on fundamental graph searches has shown that these searches all possess similar characterizations. We hope that these characterizations will lead to new simpler algorithms.
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
7671-2006
Name nom
Corneil, Derek
Department département
Computer Science
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2006
Competition year année de concours
2006
Award amount
62000
Program id
RGPIN
Program name 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
1
Nb partie
5
Application title
Algorithmic graph theory
Keyword
NA
Application summary
A graph is a mathematical object consisting of a set of nodes together with a set of edges, each joining a pair of nodes. Graphs can be used to model many different types of networks, for example Protein-Protein Interaction (PPI) networks (the nodes are proteins and an edge between two proteins indicates that the proteins interact). The first job of a graph theorist is to determine the type of graph that occurs in practical instances of the application. In the case of PPI networks, we have recently shown that the model that most closely captures the currently available biological information is geometric random graphs, not scale-free graphs as presently accepted. Once a good model has been identified, the next step is to design fast, easily implementable algorithms to solve various problems on the particular model. Such algorithms often have to work on huge data sets, as anticipated for PPI networks. My research includes the study of restricted families of graphs that arise in practice and to design fast practical algorithms. One of the fundamental algorithmic notions in graph theory is searching, i.e. following a particular algorithm to visit all nodes and edges of the graph. Many graph algorithms include some aspect of graph searching, and we've recently determined that many other problems can be solved most efficiently using multi-sweep search algorithms. Our work on fundamental graph searches has shown that these searches all possess similar characterizations. We hope that these characterizations will lead to new simpler algorithms.