并行计算在计算最小皇后独立支配集的研究

发布时间：2018-01-25 09:33

  本文关键词： 回溯 并行计算 非阻塞通信　出处：《内蒙古农业大学》2012年硕士论文　论文类型：学位论文

【摘要】：并行计算拥有有强大的数值计算和处理数据的能力,在现实生活中有着广泛的应用,如地震的预测和预报、石油的勘探、气候的模拟、武器方面的设计、核武器系统的研究与模拟、航空和航天飞行器的设计、卫星图像的处理、天体和地球的科学、虚拟现实的系统和电影的动画系统等。 棋盘支配问题开启了图的支配集问题的研究,直到1962年才由Berge和Ore出版的书中给出了一些最基本的数学定义。即使是最早的棋盘支配问题研究起来也是相当困难的,到目前来说许多问题大部分还没有完全解决。这些悬而未决的问题在十九世纪七十年代促进了图的支配集问题的研究,其中最有趣和最困难的就是皇后支配集问题。 并行计算的发展为解决图论中的一些难题提供给了可能,图论中的一些难题是可以借助并行计算机来得到解决。本文就是在最小皇后独立支配集串行算法的基础上提出了一个并行的算法,在集群这个平台上实现了对最小皇后独立支配集的并行计算。
[Abstract]:Parallel computing has powerful numerical computing and data processing ability, and has been widely used in real life, such as earthquake prediction and prediction, oil exploration, climate simulation, weapon design. Nuclear weapon system research and simulation, aerospace aircraft design, satellite image processing, celestial and Earth science, virtual reality system and movie animation system. The chessboard domination problem opens up the study of the dominating set problem of graphs. It was not until 1962 that some basic mathematical definitions were given in the books published by Berge and Ore. Even the earliest problems of chessboard domination were difficult to study. Up to now, most of the problems have not been solved completely. In 1870s, these outstanding problems promoted the study of the dominating set problem of graphs. One of the most interesting and difficult is the question of the Queen's domination set. The development of parallel computing makes it possible to solve some difficult problems in graph theory. Some difficult problems in graph theory can be solved by parallel computers. This paper proposes a parallel algorithm based on the serial algorithm of the minimal queen independent dominating set. On the platform of cluster, the parallel computation of the minimum queen independent dominating set is realized.
【学位授予单位】：内蒙古农业大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP338.6;O157.5

【相似文献】

相关期刊论文 前10条

1 张光铎，，王正志;图论中独立支配集的最佳求解算法研究[J];国防科技大学学报;1995年02期

2 张剑英,周三明;与图的支配性有关的不变量的若干不等式[J];华中理工大学学报;1996年11期

3 莫忠息;图论中独立支配集的求解问题并未解决[J];数学研究与评论;1999年01期

4 蔡延光 ,罗狄隐;树的两类m—路中心[J];湖北汽车工业学院学报;1992年01期

5 赵亚谷;关于图的支配划分的两个猜测[J];数学研究与评论;1986年03期

6 路纲;周明天;唐勇;吴振强;裘国永;袁柳;;任意图支配集精确算法回顾[J];计算机学报;2010年06期

7 蔡延光;图的增广支配数[J];湖北汽车工业学院学报;1999年01期

8 罗朝阳;曹香兰;李虎;;一些特殊图类的Kronecker乘积的参数[J];昌吉学院学报;2010年02期

9 王福军,程建钢,姚振汉;结构非线性动力分析显式积分并行算法[J];清华大学学报(自然科学版);2002年04期

10 冯诗齐;用并行计算构建一个虚拟太空[J];世界科学;2002年10期

相关会议论文 前10条

1 齐进;叶文华;;三维激光烧蚀瑞利-泰勒不稳定性并行计算[A];中国空气动力学学会第十届物理气体动力学专业委员会会议论文集[C];2001年

2 范晓樯;李桦;田正雨;;超声速/高超声速飞行器复杂流场大规模并行数值仿真[A];计算流体力学研究进展——第十二届全国计算流体力学会议论文集[C];2004年

3 张望;王辉;;个性化服务中的并行K-Means聚类算法[A];2007年全国开放式分布与并行计算机学术会议论文集(下册)[C];2007年

4 丛鹏;;MPI并行计算实现工业CT图像重建[A];2004年CT和三维成像学术年会论文集[C];2004年

5 丁国昊;罗凯;李伟;李桦;;乘波飞行器气动特性数值模拟与并行计算[A];第三届高超声速科技学术会议会议文集[C];2010年

6 唐维军;张景琳;蔚喜军;;三维流体界面不稳定性的并行计算[A];中国工程物理研究院科技年报（2000）[C];2000年

7 左风丽;莫则尧;叶文华;;计算流体三维分裂格式的高效并行计算[A];中国工程物理研究院科技年报（2003）[C];2003年

8 罗文彩;陈小前;;并行计算的多方法优化协作[A];第二十四届中国控制会议论文集（上册）[C];2005年

9 杜志文;曾文华;;网格计算在文本分类中的应用[A];2006年全国开放式分布与并行计算机学术会议论文集（三）[C];2006年

10 耿江东;薛正辉;高本庆;;应用并行GTD算法计算阵列天线近场受扰[A];第17届全国电磁兼容学术会议论文集[C];2007年

相关重要报纸文章 前10条

1 江锡民;英特尔并行计算中心落户无锡[N];新华日报;2009年

2 轶嘉;英特尔全球首个并行计算中心落户无锡[N];人民邮电;2009年

3 刘琦;伯克利专家展望未来并行计算[N];中国计算机报;2008年

4 均儿;通用计算核动力[N];电脑报;2009年

5 英特尔并行计算实验室研究员 TimothyMattson;并行计算:减少串行软件[N];中国计算机报;2007年

6 本报记者 马文方;英特尔为何要牵头并行计算[N];中国计算机报;2009年

7 英特尔 赵军(Jun Zhao);PC机并行计算革命尚未成功[N];中国计算机报;2009年

8 ;并行计算成PC产业发展瓶颈[N];人民邮电;2008年

9 刘霞;计算能力的提升需要一场革命[N];科技日报;2010年

10 向东;让并购增值：一切取决于管理[N];江苏经济报;2005年

相关博士学位论文 前10条

1 于瑞云;无线传感器网络中面向数据采集的支配集算法与策略研究[D];东北大学;2009年

2 骆伟忠;无线网络中若干NP-难问题的参数算法[D];中南大学;2012年

3 施韦;移动Ad Hoc网络中连通支配集若干关键问题的研究[D];浙江大学;2007年

4 路纲;无线自组织网络拓扑结构研究[D];电子科技大学;2009年

5 陈军;分布式存储环境下并行计算可扩展性的研究与应用[D];中国人民解放军国防科学技术大学;2000年

6 阎新芳;无线Ad hoc网络分层路由问题研究[D];天津大学;2005年

7 陈晓春;基于并行计算的大涡模拟方法及其工程应用基础研究[D];西安建筑科技大学;2004年

8 王开健;基于特大增量步算法的网络并行计算[D];清华大学;2005年

9 尹欣;三维弹性问题边界元法并行计算及其工程应用[D];清华大学;2000年

10 张理论;面向气象预报数值模式的高效并行计算研究[D];中国人民解放军国防科学技术大学;2002年

相关硕士学位论文 前10条

1 马俊清;并行计算在计算最小皇后独立支配集的研究[D];内蒙古农业大学;2012年

2 王R

本文编号：1462577