Structural and Algorithmic Aspects of Graphs

图的结构和算法方面

基本信息

  • 批准号:
    RGPIN-2017-04053
  • 负责人:
  • 金额:
    $ 1.02万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2018
  • 资助国家:
    加拿大
  • 起止时间:
    2018-01-01 至 2019-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.*****
我的研究兴趣是计算组合学,主要研究有限对象。我花了大部分时间研究的对象类型是图表。许多实际问题,如任务调度、通信网络设计、交通控制等,都可以用图来建模。问题的有效计算解决方案往往可以从对图的结构性质的理解中得到。图论在许多其他科学中也被证明是有用的。例如,计算机科学与图论密切相关。开发有效的算法来解决图上的问题是计算机科学家的主要兴趣。当然,并不是所有图上的问题都有有效的算法。人们普遍认为某些问题没有有效的解决办法,但要证明这一点本身就是一个问题。克莱数学研究所(Clay Mathematics Institute)作为千禧年奖问题之一提出的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其他文献

Energy-Efficient Resource Utilization for Heterogeneous Embedded Computing Systems
异构嵌入式计算系统的节能资源利用
  • DOI:
    10.1109/tc.2017.2693186
  • 发表时间:
    2017-09-01
  • 期刊:
  • 影响因子:
    3.7
  • 作者:
    Huang, Jing;Li, Renfa;Li, Keqin
  • 通讯作者:
    Li, Keqin
Comparisons of personal exposure to PM2.5 and CO by different commuting modes in Beijing, China
中国北京不同通勤方式PM2.5和CO个人暴露量比较
  • DOI:
    10.1016/j.scitotenv.2012.03.007
  • 发表时间:
    2012-05-15
  • 期刊:
  • 影响因子:
    9.8
  • 作者:
    Huang, Jing;Deng, Furong;Guo, Xinbiao
  • 通讯作者:
    Guo, Xinbiao
Photonic Ionic Liquids Polymer for Naked-Eye Detection of Anions
用于肉眼检测阴离子的光子离子液体聚合物
  • DOI:
    10.1002/adma.200800808
  • 发表时间:
    2008-11-03
  • 期刊:
  • 影响因子:
    29.4
  • 作者:
    Hu, Xiaobin;Huang, Jing;Li, Guangtao
  • 通讯作者:
    Li, Guangtao
HASF is a stem cell paracrine factor that activates PKC epsilon mediated cytoprotection.
  • DOI:
    10.1016/j.yjmcc.2013.11.010
  • 发表时间:
    2014-01
  • 期刊:
  • 影响因子:
    5
  • 作者:
    Huang, Jing;Guo, Jian;Beigi, Farideh;Hodgkinson, Conrad P.;Facundo, Heberty T.;Zhang, Zhiping;Espinoza-Derout, Jorge;Zhou, Xiyou;Pratt, Richard E.;Mirotsou, Maria;Dzau, Victor J.
  • 通讯作者:
    Dzau, Victor J.
Key Disaster-Causing Factors Chains on Urban Flood Risk Based on Bayesian Network
基于贝叶斯网络的城市洪水风险关键致灾因素链
  • DOI:
    10.3390/land10020210
  • 发表时间:
    2021-02-01
  • 期刊:
  • 影响因子:
    3.9
  • 作者:
    Huang, Shanqing;Wang, Huimin;Huang, Jing
  • 通讯作者:
    Huang, Jing

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
  • 财政年份:
    2020
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Structural and Algorithmic Aspects of Graphs
图的结构和算法方面
  • 批准号:
    RGPIN-2017-04053
  • 财政年份:
    2019
  • 资助金额:
    $ 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

相似国自然基金

高温蠕变与疲劳协同作用下多裂纹扩展寿命算法研究
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
数智赋能的重特大突发事件食药类物资分配与再分配联动优化模型和算法
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
信息推送技术的深度网络融合与模糊学习优化研究
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
基于智能优化算法的糖尿病诊疗决策模型构建及应用——融合重庆三甲医院临床数据
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
异构无线传感器网络传输路径与时序算法研究
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
基于LSTM-注意力机制的教学场景自适应融合算法研究——课堂教学质量的实时诊断与优化
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
基于主客观融合的智能汽车主动避障控制研究
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
高效安全大规模分布式学习算法研究
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
山地环境下的无人机视觉定位算法研究与验证
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
基于混合遗传算法的社区养老物资动态配送路径优化研究与应用
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目

相似海外基金

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
  • 财政年份:
    2020
  • 资助金额:
    $ 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
  • 财政年份:
    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 }}

知道了