斯坦纳树填装数猜想与图的树连通度

批准号:
11601254
项目类别:
青年科学基金项目
资助金额:
19.0 万元
负责人:
毛亚平
依托单位:
学科分类:
A0409.图论及其应用
结题年份:
2019
批准年份:
2016
项目状态:
已结题
项目参与者:
李贺、贾楠、郭志伟
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
微信扫码咨询
中文摘要
Nash-Williams-Tutte定理既是结构图论中的经典结果,又是生成树填装问题研究中的重要工具。作为生成树的自然推广,斯坦纳树在大规模集成电路设计和网络科学方面有着重要应用。Kriesell在2013年提出的关于斯坦纳树填装问题的猜想是Nash-Williams-Tutte定理的推广。在这个猜想的带动下,学者们在近10多年里取得了一些重要进展,同时也获得了一些方法和技巧。与此同时,West和Wu在2012年提出了关于S-连通子的猜想。目前,这两个猜想仍然没有解决。树连通度是经典连通度的推广,是斯坦纳树填装问题方面的另一个图参数。. 本项目运用经典结构图论和极值图论诸多研究工具和代数方法研究Kriesell猜想,West-Wu猜想和树连通度。
英文摘要
The Nash-Williams-Tutte Theorem about spanning-tree packing problem is both a classical result and an important tool in structural graph theory. Steiner tree is a natural generalization of spanning tree and is popularly used in the physical design of VLSI circuits and network science. In 2003, Kriesell proposed a conjecture about Steiner tree packing problem, which can be seen as a generalization of the Nash-Williams-Tutte Theorem. Motivated by this conjecture, researchers have made important progress and obtained some technical methods in recent ten years. Also, West and Wu in 2012 proposed a new conjecture about S-connector. These conjectures are still open now. Tree-connectivity is a generalization of classical connectivity, which is another structural parameter of Steiner tree packing problem.. In this project, we are devoted to study Kriesell conjecture, West-Wu conjecture and tree-connectivity by classical tools in structural graph theory, extremal graph theory and algebra theory.
斯坦纳树在大规模集成电路设计和网络科学方面有着重要应用。本项目主要研究Kriesell 猜想、West-Wu 猜想和斯坦纳结构参数。前者与Kriesell猜想和Nash-Williams-Tutte定理紧密联系,是衡量网络安全性和可靠性的重要参数。后者在多处理器计算机网络方面和数学化学方面有着重要应用。. 本项目重要研究成果:1.获得了West-Wu 猜想的相关进展和结果。2.系统研究了斯坦纳维纳指标参数,并且研究了其在数学化学方面的应用。3. 利用本项目产生的新方法,对一般图的匹配排除集参数进行系统研究,为理论计算科学方面的特殊网络研究提供了理论和方法参考。.在斯坦纳结构参数方面,进行了广义连通度、悬挂树连通度和路连通度的算法复杂性分析,获得了Menger类型结果,研究了界问题、Nordhaus-Gaddum类型问题和极值问题,获得了一些研究新方法。. 受欧洲科学院院士Ivan Gutman教授邀请,主持人与其他国外专家一起撰写发表了数学化学学科的学术专著《Bounds in Chemical Graph Theory-Advances》,该专著是“Mathematical Chemistry Monographs”系列图书之一,系列图书旨在推动数学,特别是离散数学,应用于化学分子现象研究的发展。主持人毛亚平受邀专著题目为《Nordhaus-Gaddum Type Results in Chemical Graph Theory》(126页),主要介绍了数学化学Nordhaus-Gaddum类型问题的研究背景和意义,总结了该方面几十年来的国际研究成果,同时提出了进一步研究的猜想和公开问题。. 依托本项目,出版专著1部;发表论文25篇,其中SCI论文23篇;举办国际学术会议6次;成员赴国外学习4次;项目主持人获得5项省部级以上奖励或荣誉称号,担任国际国内兼职8项;培养硕士研究生9名,培养博士研究生1名;3名项目研究生成员正在攻读博士研究生(荷兰屯特大学、西安电子科技大学、青海师范大学)。
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
DOI:10.1016/j.tcs.2018.06.050
发表时间:2019-01
期刊:Theoretical Computer Scince
影响因子:--
作者:王兆;Christopher Melekian;Eddie Cheng;毛亚平
通讯作者:毛亚平
Steiner (revised) Szeged index of graphs
Steiner(修订版)Szeged 图表索引
DOI:--
发表时间:2019-05
期刊:MATCH Commun. Math. Comput. Chem.
影响因子:--
作者:M. Ghorbani;Xueliang Li;H.R. Maimani;Y.P. Mao;S. Rahmani;M. Rajabi-Parsa
通讯作者:M. Rajabi-Parsa
DOI:10.2478/auom-2019-0020
发表时间:2019-06
期刊:Analele Universitatii "Ovidius" Constanta - Seria Matematica
影响因子:--
作者:Y. Mao;Zhao Wang;K. Das
通讯作者:Y. Mao;Zhao Wang;K. Das
Graphs with given k-independence number
具有给定 k 独立数的图
DOI:--
发表时间:2018
期刊:Utilitas Mathematica
影响因子:--
作者:王兆;蔡俊亮;毛亚平
通讯作者:毛亚平
DOI:10.1016/j.dam.2018.08.006
发表时间:2019-02
期刊:Discrete Applied Mathematics
影响因子:1.1
作者:Chang Hong;Huang Zhong;Li Xueliang;Mao Yaping;Zhao Haixing
通讯作者:Zhao Haixing
拉姆齐理论和加莱-拉姆齐数及其应用研究
- 批准号:--
- 项目类别:--
- 资助金额:34万元
- 批准年份:2020
- 负责人:毛亚平
- 依托单位:
国内基金
海外基金
