Structural and Algorithmic Aspects of Graphs

图的结构和算法方面

基本信息

  • 批准号:
    RGPIN-2017-04053
  • 负责人:
  • 金额:
    $ 1.02万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2020
  • 资助国家:
    加拿大
  • 起止时间:
    2020-01-01 至 2021-12-31
  • 项目状态:
    已结题

项目摘要

My research interest lies in computational combinatorics, which deals with mostly finite objects. The type of objects that I spent most of time studying are graphs. Many problems of practical interest, such as scheduling of tasks, communication network design, traffic control, etc., can be modelled by graphs. Efficient computational solutions of problems can often be derived from an 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 major interest to computer scientists. Of course, not all problems on graphs have been shown to admit efficient algorithms. It is generally believed that certain problems do not admit efficient solutions, but to prove this is the case is a problem by itself. The P vs NP problem, established by Clay Mathematics Institute as one of the Millennium Prize Problems, reflects exactly this situation. My long-term goal is an on-going study of combinatorial problems from both the structural and computational points of view. The P vs NP problem is considered to be very difficult at the moment. I anticipate a theory will be developed 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 results concerning the structure of combinatorial objects and using the structural properties to derive dichotomy type of theorems, which hopefully will form building blocks for the anticipated theory. Graph searching is fundamental in exploring graphs and detecting their structures. Deciding which vertices of a graph can be end-vertices of a specific graph search is a problem that has been actively studied in the recent years. Several results which characterize end-vertices of certain searches have been obtained for some classes of graphs. However, the end-vertex problem is still open for 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 be completed to an oriented graph that satisfies a prescribed property is a fundamental problem which generalizes several existing problems. Graph colouring is a central topic in graph theory and has applications in real life. Colouring problems are special partition problems which are hard in general. Discovering graph classes for which these problems admit efficient algorithmic solutions is 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.
我的研究兴趣在于计算组合学,它主要处理有限对象。我花大部分时间研究的对象类型是图形。许多实际问题,如任务调度、通信网络设计、流量控制等,都可以用图表来表示。问题的有效计算解决方案通常可以从对图的结构性质的理解中得出。图论在许多其他科学中也被证明是有用的。例如,计算机科学与图论有着非常密切的关系。开发有效的算法来解决图上的问题是计算机科学家的主要兴趣。当然,并不是所有的图上的问题都有有效的算法。人们普遍认为,某些问题不承认有效的解决方案,但要证明这是一个问题本身。由克莱数学研究所设立的千年奖难题之一的P vs NP问题,正是这种情况的反映。 我的长期目标是从结构和计算的角度对组合问题进行持续的研究。P vs NP问题目前被认为是非常困难的。我预料在解决这个难题的过程中会沿着发展出一种理论。我想为建立这样一个理论做出贡献。因此,我的目标是继续生产有关组合对象的结构的数学结果,并使用的结构特性,以获得二分法类型的定理,这希望将形成预期的理论积木。 图搜索是探索图和检测其结构的基础。决定图的哪些顶点可以是特定图搜索的端顶点是近年来一直在积极研究的问题。对于某些图类,已经得到了几个刻画某些搜索的端点的结果。然而,端点问题仍然是开放的许多类别的图。 图的结构有时在它们的方向属性中是固有的;某些图只能承认某些方向。判定一个部分有向图是否可以完备为满足给定性质的有向图是一个基本问题,它是现有问题的推广。 图着色是图论中的一个中心课题,在真实的生活中有着广泛的应用。着色问题是一种特殊的划分问题,一般来说比较困难。发现这些问题承认有效的算法解决方案的图形类是可取的,并在真实的生活中有潜在的应用。 作为短期目标,我将继续研究这三类问题,即,各种图搜索算法的端点问题、方向完成问题和广义图着色问题。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Huang, Jing其他文献

Development of Highly Potent Noncovalent Inhibitors of SARS-CoV-2 3CLpro.
  • DOI:
    10.1021/acscentsci.2c01359
  • 发表时间:
    2023-02-22
  • 期刊:
  • 影响因子:
    18.2
  • 作者:
    Hou, Ningke;Shuai, Lei;Zhang, Lijing;Xie, Xuping;Tang, Kaiming;Zhu, Yunkai;Yu, Yin;Zhang, Wenyi;Tan, Qiaozhu;Zhong, Gongxun;Wen, Zhiyuan;Wang, Chong;He, Xijun;Huo, Hong;Gao, Haishan;Xu, You;Xue, Jing;Peng, Chen;Zou, Jing;Schindewolf, Craig;Menachery, Vineet;Su, Wenji;Yuan, Youlang;Shen, Zuyuan;Zhang, Rong;Yuan, Shuofeng;Yu, Hongtao;Shi, Pei-Yong;Bu, Zhigao;Huang, Jing;Hu, Qi
  • 通讯作者:
    Hu, Qi
ENERGETIC ELECTRON PROPAGATION IN THE DECAY PHASE OF NON-THERMAL FLARE EMISSION
非热耀斑发射衰变阶段的高能电子传播
  • DOI:
    10.1088/0004-637x/787/2/123
  • 发表时间:
    2014-05
  • 期刊:
  • 影响因子:
    4.9
  • 作者:
    Huang, Jing;Yan, Yihua;Tsap, Yuri T.
  • 通讯作者:
    Tsap, Yuri T.
Highly efficient heterogeneous photo-Fenton BiOCl/MIL-100(Fe) nanoscaled hybrid catalysts prepared by green one-step coprecipitation for degradation of organic contaminants.
  • DOI:
    10.1039/d1ra06549a
  • 发表时间:
    2021-09-27
  • 期刊:
  • 影响因子:
    3.9
  • 作者:
    Wu, Doufeng;Jiang, Jiantang;Tian, Nini;Wang, Mei;Huang, Jing;Yu, Deyou;Wu, Minghua;Ni, Huagang;Ye, Peng
  • 通讯作者:
    Ye, Peng
Morphological analysis of the alveolar bone of the anterior teeth in severe high-angle skeletal Class II and Class III malocclusions assessed with cone-beam computed tomography
  • DOI:
    10.1371/journal.pone.0210461
  • 发表时间:
    2019-03-25
  • 期刊:
  • 影响因子:
    3.7
  • 作者:
    Ma, Jing;Huang, Jing;Jiang, Jiu-hui
  • 通讯作者:
    Jiang, Jiu-hui
AI Empowered Virtual Reality Integrated Systems for Sleep Stage Classification and Quality Enhancement

Huang, Jing的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Huang, Jing', 18)}}的其他基金

Structural and Algorithmic Aspects of Graphs
图的结构和算法方面
  • 批准号:
    RGPIN-2017-04053
  • 财政年份:
    2022
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Structural and Algorithmic Aspects of Graphs
图的结构和算法方面
  • 批准号:
    RGPIN-2017-04053
  • 财政年份:
    2021
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Structural and Algorithmic Aspects of Graphs
图的结构和算法方面
  • 批准号:
    RGPIN-2017-04053
  • 财政年份:
    2019
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Structural and Algorithmic Aspects of Graphs
图的结构和算法方面
  • 批准号:
    RGPIN-2017-04053
  • 财政年份:
    2018
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Stress response regulation by Eukaryotic elongation factor-2 kinase efk-1/eEF2K in C. elegans
线虫中真核延伸因子 2 激酶 efk-1/eEF2K 的应激反应调节
  • 批准号:
    527389-2018
  • 财政年份:
    2018
  • 资助金额:
    $ 1.02万
  • 项目类别:
    University Undergraduate Student Research Awards
Structural and Algorithmic Aspects of Graphs
图的结构和算法方面
  • 批准号:
    RGPIN-2017-04053
  • 财政年份:
    2017
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithmic and Structural Graph Theory
算法和结构图论
  • 批准号:
    203191-2012
  • 财政年份:
    2016
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithmic and Structural Graph Theory
算法和结构图论
  • 批准号:
    203191-2012
  • 财政年份:
    2015
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithmic and Structural Graph Theory
算法和结构图论
  • 批准号:
    203191-2012
  • 财政年份:
    2014
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithmic and Structural Graph Theory
算法和结构图论
  • 批准号:
    203191-2012
  • 财政年份:
    2013
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual

相似海外基金

Combinational, Structural and algorithmic aspects of temporal graphs
时间图的组合、结构和算法方面
  • 批准号:
    2903280
  • 财政年份:
    2024
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Studentship
Structural and Algorithmic Aspects of Graphs
图的结构和算法方面
  • 批准号:
    RGPIN-2017-04053
  • 财政年份:
    2022
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Structural and Algorithmic Aspects of Graphs
图的结构和算法方面
  • 批准号:
    RGPIN-2017-04053
  • 财政年份:
    2021
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Structural and Algorithmic Aspects of Graphs
图的结构和算法方面
  • 批准号:
    RGPIN-2017-04053
  • 财政年份:
    2019
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Structural and Algorithmic Aspects of Graphs
图的结构和算法方面
  • 批准号:
    RGPIN-2017-04053
  • 财政年份:
    2018
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Structural and Algorithmic Aspects of Graphs
图的结构和算法方面
  • 批准号:
    RGPIN-2017-04053
  • 财政年份:
    2017
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithmic and structural aspects of combinatorics
组合数学的算法和结构方面
  • 批准号:
    203191-1998
  • 财政年份:
    2001
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithmic and structural aspects of combinatorics
组合数学的算法和结构方面
  • 批准号:
    203191-1998
  • 财政年份:
    2000
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithmic and structural aspects of combinatorics
组合数学的算法和结构方面
  • 批准号:
    203191-1998
  • 财政年份:
    1999
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithmic and structural aspects of combinatorics
组合数学的算法和结构方面
  • 批准号:
    203191-1998
  • 财政年份:
    1998
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了