Grant: Discovery Grants Program - Individual
University of Toronto
$33,000.00
Algorithmic graph theory
EF 2014-15
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 social networks where the nodes are people and the edges represent friendship; thus there is an edge between the nodes representing Jack and Jill if and only if Jack and Jill are friends. Graphs can also have directed edges, for example suppose the nodes are jobs that have to be run on a computer and a directed edge from J1 to J2 indicates that job J1 must be completed before job J2 can start. Clearly, if there is an edge from Ji to Jj and an edge from Jj to Jk, then there must be an edge from Ji to Jk. Given a graph for some application, one then wants to construct algorithms that solve specific problems on the graph. In the ""friendship network"", we may want to find a largest set of people who are mutually friends; in the second example we may want to find a fastest possible schedule that will assign each job to one of two computers such that if there is an edge from Ji to Jj, then both jobs must be on the same computer and Ji must be scheduled before Jj. When one is faced with designing such algorithms, the first task is to determine properties of the given graph and then to design algorithms that exploit these properties.My research includes the study of restricted families of graphs that arise in practice and the design of fast, practical algorithms. One of the fundamental algorithmic notions in graph theory is searching a graph, namely following a particular algorithm to visit all nodes and edges of the graph. Many graph algorithms employ some aspect of graph searching and recently we've found many new algorithms that are built off graph searching. These algorithms are efficient and easy to implement; furthermore, they often involve multi-sweep searches where we do one search and then use it to determine the next search etc. Lexicographic Breadth First Search is currently the most popular such search strategy; however, recently we have found exciting applications of Lexicographic Depth First 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
7671-2011
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
2014
Competition year année de concours
2011
Award amount
33000
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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
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
4
Nb partie
5
Application title
Algorithmic graph theory
Keyword
NSERC
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 social networks where the nodes are people and the edges represent friendship; thus there is an edge between the nodes representing Jack and Jill if and only if Jack and Jill are friends. Graphs can also have directed edges, for example suppose the nodes are jobs that have to be run on a computer and a directed edge from J1 to J2 indicates that job J1 must be completed before job J2 can start. Clearly, if there is an edge from Ji to Jj and an edge from Jj to Jk, then there must be an edge from Ji to Jk. Given a graph for some application, one then wants to construct algorithms that solve specific problems on the graph. In the ""friendship network"", we may want to find a largest set of people who are mutually friends; in the second example we may want to find a fastest possible schedule that will assign each job to one of two computers such that if there is an edge from Ji to Jj, then both jobs must be on the same computer and Ji must be scheduled before Jj. When one is faced with designing such algorithms, the first task is to determine properties of the given graph and then to design algorithms that exploit these properties.My research includes the study of restricted families of graphs that arise in practice and the design of fast, practical algorithms. One of the fundamental algorithmic notions in graph theory is searching a graph, namely following a particular algorithm to visit all nodes and edges of the graph. Many graph algorithms employ some aspect of graph searching and recently we've found many new algorithms that are built off graph searching. These algorithms are efficient and easy to implement; furthermore, they often involve multi-sweep searches where we do one search and then use it to determine the next search etc. Lexicographic Breadth First Search is currently the most popular such search strategy; however, recently we have found exciting applications of Lexicographic Depth First Search.