Rectilinear Crossing Number

来自中国分布式计算总站
Fwjmath讨论 | 贡献2008年3月1日 (六) 18:44的版本 (新页面: <big>'''Rectilinear Crossing Number'''</big><br> '''寻找平面化完全图最小交叉数'''<br> ==项目简介== Rectilinear Crossing Number是由[http://www.tugraz.at/ 奥地利...)
(差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)
跳转到导航 跳转到搜索

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

项目简介

Rectilinear Crossing Number是由奥地利格拉茨技术大学运作的,基于 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 位计算程序。

相关链接

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