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

来自中国分布式计算总站
跳转至: 导航搜索
项目简介
第17行: 第17行:
 
[http://dist.ist.tugraz.at/cape5/ 官方网站]<br>
 
[http://dist.ist.tugraz.at/cape5/ 官方网站]<br>
 
[http://www.equn.com/forum/viewthread.php?tid=14688&pid=207584&page=1&extra=page%3D1#pid219468 项目新闻中文翻译]
 
[http://www.equn.com/forum/viewthread.php?tid=14688&pid=207584&page=1&extra=page%3D1#pid219468 项目新闻中文翻译]
[[category:分布式计算项目]][[category:数学类项目]][[category:BOINC平台上的项目]]
+
 
 +
[[category:项目]]
 +
[[category:数学]]
 +
[[category:BOINC]]

2008年6月26日 (四) 14:49的版本

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 位计算程序。

相关链接

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