Rectilinear Crossing Number
跳转到导航
跳转到搜索
Rectilinear Crossing Number
寻找平面化完全图最小交叉数
项目简介
Rectilinear Crossing Number（通常缩写为RCN）是由奥地利格拉茨技术大学运作的，基于BOINC平台的分布式计算项目。Rectilinear Crossing Number的目标是尝试借助BOINC能召集的计算力来寻找平面化完全图最小交叉数。目前项目已经得到了阶数小于等于17的完全图的交叉数，还有直到阶数为100的完全图交叉数的一些下界。目前项目正在进行对于18阶完全图的搜索。
如何加入项目
该项目基于 BOINC 平台，简要的加入步骤如下（已完成的步骤可直接跳过）：
- 下载并安装 BOINC 的客户端软件（官方下载页面或程序下载）
- 点击客户端简易视图下的“Add Project”按钮，或高级视图下菜单中的“工具->加入项目”，将显示向导对话框
- 点击下一步后在项目列表中找到并单击选中 Rectilinear Crossing Number 项目（如未显示该项目，则在编辑框中输入项目网址：http://dist.ist.tugraz.at/cape5/ ），然后点击下一步
- 输入您可用的电子邮件地址，并设置您在该项目的登录密码（并非您的电子邮件密码）
- 再次点击下一步，如项目服务器工作正常（并且有适合自身操作系统的计算程序），即已成功加入项目
更详细的加入方法说明，请访问 BOINC 新手指南 或 BOINC 使用教程。
本站推荐您加入 Team China 团队，请访问项目官方网站的 团队检索页面，搜索（Search）并进入 Team China 的团队页面，点击页面中的 Join 并输入用户登录信息即可加入！
项目研究内容简介与成果
在图论，交叉数是指一个图在平面上，边的交叉点的最小数目。一个图在平面上可以有多种画法，若有多于两条边相交于同一点，每对相交边计算一次。给定一个图，计算其交叉数是一个NP-hard的问题。Rectilinear Crossing Number想要解决的就是这个问题的一个特殊情况，也就是当图为完全图时候的情况。目前项目已经得到了阶数小于等于17的完全图的交叉数，还有直到阶数为100的完全图交叉数的一些下界，详细的结果请参看这里（英文）。
计算程序
Rectilinear Crossing Number提供 Windows, Linux, Mac OS X 上的 32 位计算程序。