“Rectilinear Crossing Number”的版本间的差异

来自中国分布式计算总站
跳转至: 导航搜索
项目简介
项目简介
第2行: 第2行:
 
'''寻找平面化完全图最小交叉数'''<br>
 
'''寻找平面化完全图最小交叉数'''<br>
 
==项目简介==
 
==项目简介==
[[Rectilinear Crossing Number]]是由[http://www.tugraz.at/ 奥地利格拉茨技术大学]运作的,基于[[BOINC]]平台的分布式计算项目。[[Rectilinear Crossing Number]]的目标是尝试借助[[BOINC]]能召集的计算力来寻找平面化完全图最小交叉数。目前项目已经得到了阶数小于等于17的完全图的交叉数,还有直到阶数为100的完全图交叉数的一些下界。目前项目正在进行对于18阶完全图的搜索。
+
[[Rectilinear Crossing Number]](通常缩写为[[RCN]])是由[http://www.tugraz.at/ 奥地利格拉茨技术大学]运作的,基于[[BOINC]]平台的分布式计算项目。[[Rectilinear Crossing Number]]的目标是尝试借助[[BOINC]]能召集的计算力来寻找平面化完全图最小交叉数。目前项目已经得到了阶数小于等于17的完全图的交叉数,还有直到阶数为100的完全图交叉数的一些下界。目前项目正在进行对于18阶完全图的搜索。
 
<br><br>
 
<br><br>
  

2008年3月2日 (日) 15:34的版本

Rectilinear Crossing Number
寻找平面化完全图最小交叉数

项目简介

Rectilinear Crossing Number(通常缩写为RCN)是由奥地利格拉茨技术大学运作的,基于BOINC平台的分布式计算项目。Rectilinear Crossing Number的目标是尝试借助BOINC能召集的计算力来寻找平面化完全图最小交叉数。目前项目已经得到了阶数小于等于17的完全图的交叉数,还有直到阶数为100的完全图交叉数的一些下界。目前项目正在进行对于18阶完全图的搜索。

加入方法

本项目运行在分布式平台BOINC上,希望加入该项目的请参见BOINC新手指南。项目网址为 http://dist.ist.tugraz.at/cape5/

项目研究内容简介与成果

在图论,交叉数是指一个图在平面上,边的交叉点的最小数目。一个图在平面上可以有多种画法,若有多于两条边相交于同一点,每对相交边计算一次。给定一个图,计算其交叉数是一个NP-hard的问题。Rectilinear Crossing Number想要解决的就是这个问题的一个特殊情况,也就是当图为完全图时候的情况。目前项目已经得到了阶数小于等于17的完全图的交叉数,还有直到阶数为100的完全图交叉数的一些下界,详细的结果请参看这里(英文)

计算程序

Rectilinear Crossing Number提供 Windows, Linux, Mac OS X 上的 32 位计算程序。

相关链接

官方网站
项目新闻中文翻译