近乎最佳的Manhattan型Steiner树近似算法

来源 :软件学报 | 被引量 : 0次 | 上传用户：zqqv353

【摘要】

：

求解最佳的Manhattan型Steiner树问题(minimum rectilinear Steiner tree,简记为MRST问题)是在VLSI布线、网络通信中所遇到的组合优化问题,同时也是一个NP-难解问题.该文给出

【作者】

：

马军杨波马绍汉

【机构】

：

山东大学计算机科学系

【出处】

：

软件学报

【发表日期】

：

2004年期

【关键词】

：

Steiner树算法复杂性组合优化电路布线

【基金项目】

：

国家科技攻关项目

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

求解最佳的Manhattan型Steiner树问题(minimum rectilinear Steiner tree,简记为MRST问题)是在VLSI布线、网络通信中所遇到的组合优化问题,同时也是一个NP-难解问题.该文给出对该问题的O(n2)时间复杂性的近似算法.该算法在最坏情况下的近似比严格小于3/2.计算机实验结果表明,所求得的支撑树的平均费用与最佳算法的平均费用仅相差0.8%.该算法稍加修改,可应用到三维或多维的Manhattan空间对Steiner问题求解,且易于在并行与分布式环境下编程实现.

其他文献

水火弯板工艺参数优化设计

考虑曲面钢板成型所需的局部能量,应用改进的坐标轮换法,优化了焰道参数;结合曲面成型所需局部收缩量的理论计算结果,给出能量按板长方向的合理输入,并确定了最优加工方案.

期刊

水火成型工艺设计最佳化

β-丁氧酯基三氯化锡与席夫碱配合物的合成、结构与酯交换反应

合成了标题化合物n-BuO_2CCH_2CH_2SnCl_3·(2-HOC_6H_4CH=NC_6H_4-OMe-4’),通过元素分析,UV-Vis,IR和~1H NMR进行了表征。其晶体结构分析表明,该晶体属单斜晶系,空间群P2_1

期刊

β-丁氧羰乙基三氯化锡Schiff碱有机锡配合物晶体结构酯交换反应

Control of the Rendition Wavelength Shifts of Color Lippmann Holograms Recorded in Single-layer panc

Russian PFG-03C panchromatic ultra-high resolution silver-halide emulsion is regarded as the most successful material for the fabrication of color reflection ho

期刊

color holographyreflection hologramsrendition wavelengthcolor desaturation

具有单侧刚性约束的两自由度振动系统在强共振条件下的拟周期运动与混沌

采用理论分析和数值仿真相结合的方法 ,研究了一类两自由度碰撞振动系统在一种强共振条件下的Hopf分叉问题 .分析并证实了碰撞振动系统在此共振条件下可由稳定的周期 1 1振

期刊

碰撞振动映射强共振分叉拟周期振动混沌

三级相互作用下聚四亚甲氧醚链构象性质计算

用半经验势函数计算了聚四亚甲氧醚 (polytetramethyleneoxide)链在三级相互作用下的构象能 ,并用基于旋转异构态近似模型的三级相互作用近似的统计权重矩阵方法计算了该链的

期刊

三级相互作用近似旋转异构态构象能构象性质third-order interaction approximationrotational isomeri

双掺KTP型系列晶体生长及其光谱特性

采用高温溶液缓慢降温旋转籽晶法生长出一系列双掺ＫＴＰ型晶体，研究了晶体生长习性，测定了所有晶体的晶胞参数、粉末倍频效应和晶体中掺质离子的浓度．测试了晶体的Ｒａｍａｎ光谱、激发光谱、发

期刊

双掺KTP型晶体晶体生长光谱性质

反尖晶石LiNiVO4的湿法低温合成

In this paper, we report a new kind of moist chemical method for preparing LiNiVO 4 which can be used to prepare lithium ion battery for the cathode active ma

期刊

反尖晶石LiNiVO4湿法合成低温

用于结构可靠性分析中的系统描述性抽样法

在用蒙特卡罗法计算结构系统可靠性时 ,运用了系统描述性抽样法。用系统描述性抽样代替蒙特卡罗的随即抽样过程 ,从而使得计算效率与降低方差都得到了明显地改善。 When usi

期刊

结构可靠性失效概率蒙特卡罗法系统描述性抽样

二元颗粒混合物按质量取样的误差研究

二元颗粒混合物的随机取样方式有两种：一是按颗粒数目取样，二是按质量取样。本文对二元颗粒混合物按质量取样的误差进行了深入研究，详细分析了混合物的各种参数对被测组分含量取

期刊

二元颗粒混合物取样误差取样方式

若丹明B荧光增强二硫化碳高阶受激喇曼散射

利用若丹明B乙醇溶液的荧光改变了二硫化碳的一至三阶Stokes喇曼谱线的强度分布,选择性地增强了三阶Stokes喇曼谱线.在泵浦功率密度为～560MW.cm-2时,对染料摩尔浓度分别为～10-5

期刊

受激喇曼散射荧光若丹明B二硫化碳

近乎最佳的Manhattan型Steiner树近似算法

与本文相关的学术论文