Rectilinear Crossing Number：修订间差异
跳转到导航
跳转到搜索
小 →项目简介 |
|||
| 第2行： | 第2行： | ||
'''寻找平面化完全图最小交叉数'''<br> | '''寻找平面化完全图最小交叉数'''<br> | ||
==项目简介== | ==项目简介== | ||
[[Rectilinear Crossing Number]] | [[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 位计算程序。