Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Victoria

$14,000.00

Structural and Algorithmic Aspects of Graphs

FY 2017-18

Summary
My research interest lies in computational combinatorics, which deals withmostly finite objects. The type of objects that I spent most of time studyingare graphs.Many problems of practical interest, such as scheduling of tasks, communicationnetwork design, traffic control, etc., can be modelled by graphs.Efficient computational solutions of problems can often be derived froman understanding of the structural properties of graphs.The theory of graphs has also proven to be useful in many other sciences.Computer science, for example, is very closely related to graph theory.Developing efficient algorithms to solve problems on graphs is of majorinterest to computer scientists. Of course, not all problems on graphs havebeen shown to admit efficient algorithms. It is generally believed that certainproblems do not admit efficient solutions, but to prove this is the case isa problem by itself. The P vs NP problem, established by Clay MathematicsInstitute as one of the Millennium Prize Problems, reflects exactly thissituation. My long-term goal is an on-going study of combinatorial problems from boththe structural and computational points of view. The P vs NP problem isconsidered to be very difficult at the moment. I anticipate a theory will bedeveloped along the way in finding a solution to this difficult problem.I would like to make contributions toward establishing such a theory.My objectives are therefore to continue producing mathematical resultsconcerning the structure of combinatorial objects and using the structuralproperties to derive dichotomy type of theorems, which hopefully will formbuilding blocks for the anticipated theory. Graph searching is fundamental in exploring graphs and detecting theirstructures. Deciding whichvertices of a graph can be end-vertices of a specificgraph search is a problem that has been actively studied in the recent years. Several results which characterizeend-vertices of certain searches have been obtained for some classesof graphs. However, the end-vertex problem is still openfor many classes of graphs. Graph structures are sometimes inherent in their orientation properties; certain graphs can only admit certain orientations. Deciding whether a partially oriented graph can becompleted to an oriented graph that satisfies a prescribed property isa fundamental problemwhich generalizes several existing problems. Graph colouring is a central topic in graph theory and has applications in real life.Colouring problems arespecial partition problems which are hard in general.Discovering graph classes for which these problems admit efficient algorithmic solutionsis desirable and has potential applications in real life. As short-term objectives, I will continue studying these three types of problems, i.e.,end-vertex problems of various graph search algorithms,orientation completion problems, and generalized graph colouring problems.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2017-04053
Name nom
Huang, Jing
Department département
Mathematics and Statistics - Mathematics and Statistics
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2017
Award amount
14000
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
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
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
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
Structural and Algorithmic Aspects of Graphs
Keyword
NSERC
Application summary
My research interest lies in computational combinatorics, which deals withmostly finite objects. The type of objects that I spent most of time studyingare graphs.Many problems of practical interest, such as scheduling of tasks, communicationnetwork design, traffic control, etc., can be modelled by graphs.Efficient computational solutions of problems can often be derived froman understanding of the structural properties of graphs.The theory of graphs has also proven to be useful in many other sciences.Computer science, for example, is very closely related to graph theory.Developing efficient algorithms to solve problems on graphs is of majorinterest to computer scientists. Of course, not all problems on graphs havebeen shown to admit efficient algorithms. It is generally believed that certainproblems do not admit efficient solutions, but to prove this is the case isa problem by itself. The P vs NP problem, established by Clay MathematicsInstitute as one of the Millennium Prize Problems, reflects exactly thissituation. My long-term goal is an on-going study of combinatorial problems from boththe structural and computational points of view. The P vs NP problem isconsidered to be very difficult at the moment. I anticipate a theory will bedeveloped along the way in finding a solution to this difficult problem.I would like to make contributions toward establishing such a theory.My objectives are therefore to continue producing mathematical resultsconcerning the structure of combinatorial objects and using the structuralproperties to derive dichotomy type of theorems, which hopefully will formbuilding blocks for the anticipated theory. Graph searching is fundamental in exploring graphs and detecting theirstructures. Deciding whichvertices of a graph can be end-vertices of a specificgraph search is a problem that has been actively studied in the recent years. Several results which characterizeend-vertices of certain searches have been obtained for some classesof graphs. However, the end-vertex problem is still openfor many classes of graphs. Graph structures are sometimes inherent in their orientation properties; certain graphs can only admit certain orientations. Deciding whether a partially oriented graph can becompleted to an oriented graph that satisfies a prescribed property isa fundamental problemwhich generalizes several existing problems. Graph colouring is a central topic in graph theory and has applications in real life.Colouring problems arespecial partition problems which are hard in general.Discovering graph classes for which these problems admit efficient algorithmic solutionsis desirable and has potential applications in real life. As short-term objectives, I will continue studying these three types of problems, i.e.,end-vertex problems of various graph search algorithms,orientation completion problems, and generalized graph colouring problems.