“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:数学]] | ||
| + | [[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 位计算程序。