项目名称: De Brujin图和Kautz图的交叉数算法及应用研究

项目编号: No.61303023

项目类型: 青年科学基金项目

立项/批准年度: 2014

项目学科: 自动化技术、计算机技术

项目作者: 王浩丽

作者单位: 天津师范大学

项目金额: 22万元

中文摘要: 图的交叉数是图的一个重要的拓扑不变量,是衡量图的非平面性的一个重要量度。图的交叉数在网络拓扑结构设计、电路板的布线及生物工程DNA的图示等方面都有广泛的应用。确定一个图的交叉数是NP困难问题,研究它对解决一般NP困难问题有重要的借鉴意义。本项目拟对de Brujin图和Kautz图的交叉数进行研究,并给出较好的计算网络拓扑结构图的交叉数及其上界的算法,在此基础上研究一般网络拓扑图的交叉数的性质。本项目的研究对图的交叉数在网络拓扑设计、电路板设计等领域的研究有重要的理论意义和应用价值。

中文关键词: 交叉数;网络拓扑图;;;

英文摘要: The crossing number of a graph is an important topological graph invariant, which is also an important measure of measuring the non-planarity of graphs. The crossing number of graphs have a wide range of applications in various aspects such as design of network topological structure, wiring of electronic circuit board and drawing of biological engineering DNA. Determining the crossing number of a graph is a NP-hard problem and it is of important significance to solve the general NP problem. This project intends to make a study on the crossing number of de Brujin graphs and Kautz graphs, to give better algorithms to calculate the crossing numbers and upper bounds of network topology graphs, and then to study on the properties of crossing numbers of general network topology graphs. Research on the crossing number of a graph in this project is of important theoretical significance and practical application value in various fields.

英文关键词: Crossing number;Network topology structure;;;

成为VIP会员查看完整内容
0

相关内容

【博士论文】基于冲量的加速优化算法
专知会员服务
25+阅读 · 2021年11月29日
专知会员服务
212+阅读 · 2021年8月2日
专知会员服务
36+阅读 · 2020年12月22日
专知会员服务
77+阅读 · 2020年12月6日
专知会员服务
42+阅读 · 2020年7月29日
【博士论文】基于冲量的加速优化算法
专知
7+阅读 · 2021年11月29日
目标检测之殇—小目标检测
极市平台
5+阅读 · 2021年11月3日
IEEE WHISPERS大规模高光谱目标跟踪挑战赛来了!
中国图象图形学报
60+阅读 · 2020年7月8日
最全综述:基于深度学习的三维重建算法
极市平台
12+阅读 · 2020年3月17日
大盘点 | 性能最强的目标检测算法
新智元
13+阅读 · 2019年7月9日
AI综述专栏 | 基于深度学习的目标检测算法综述
人工智能前沿讲习班
12+阅读 · 2018年12月7日
一文读懂图像压缩算法
七月在线实验室
16+阅读 · 2018年5月2日
基于深度学习的目标检测算法综述
AI研习社
14+阅读 · 2018年4月25日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年4月20日
Arxiv
0+阅读 · 2022年4月18日
Arxiv
17+阅读 · 2020年11月15日
Object Detection in 20 Years: A Survey
Arxiv
48+阅读 · 2019年5月13日
Deep Anomaly Detection with Outlier Exposure
Arxiv
17+阅读 · 2018年12月21日
小贴士
相关VIP内容
【博士论文】基于冲量的加速优化算法
专知会员服务
25+阅读 · 2021年11月29日
专知会员服务
212+阅读 · 2021年8月2日
专知会员服务
36+阅读 · 2020年12月22日
专知会员服务
77+阅读 · 2020年12月6日
专知会员服务
42+阅读 · 2020年7月29日
相关资讯
【博士论文】基于冲量的加速优化算法
专知
7+阅读 · 2021年11月29日
目标检测之殇—小目标检测
极市平台
5+阅读 · 2021年11月3日
IEEE WHISPERS大规模高光谱目标跟踪挑战赛来了!
中国图象图形学报
60+阅读 · 2020年7月8日
最全综述:基于深度学习的三维重建算法
极市平台
12+阅读 · 2020年3月17日
大盘点 | 性能最强的目标检测算法
新智元
13+阅读 · 2019年7月9日
AI综述专栏 | 基于深度学习的目标检测算法综述
人工智能前沿讲习班
12+阅读 · 2018年12月7日
一文读懂图像压缩算法
七月在线实验室
16+阅读 · 2018年5月2日
基于深度学习的目标检测算法综述
AI研习社
14+阅读 · 2018年4月25日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
相关论文
微信扫码咨询专知VIP会员