关于满Steiner树问题的一个近似算法

来源 :菏泽学院学报 | 被引量 : 0次 | 上传用户：feit0679

【摘要】

：

满Steiner树问题（TST）是求解一个正则点都是叶子的最小Steiner树问题，Fabio Viduani Martinez等人给出了此问题的近似算法，它的性能比为2ρ-ρ／（3ρ-2）≈2．52，而目前求解Steiner树问题

【作者】

：

罗美菊赵传立唐恒永

【机构】

：

沈阳师范大学数学与系统科学学院

【出处】

：

菏泽学院学报

【发表日期】

：

2006年5期

【关键词】

：

满Steiner树近似算法最小Steiner树 full Steiner tree approximation algorithm minimum Ste

【基金项目】

：

国家自然科学基金资助项目（10471096）.

下载到本地 , 更方便阅读

下载此文赞助VIP

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

论文部分内容阅读

满Steiner树问题（TST）是求解一个正则点都是叶子的最小Steiner树问题，Fabio Viduani Martinez等人给出了此问题的近似算法，它的性能比为2ρ-ρ／（3ρ-2）≈2．52，而目前求解Steiner树问题的近似算法的性能比，最小值约为1．550．对满Steine。树问题给出了一个近似算法，并将它的性能比改进为2ρ-3ρ／（6ρ-2）≈2．463．

其他文献

球对称动态黑洞的广义Stefan-Boltzmann定律

选取超前爱丁顿坐标，采用统计的方法，计算出动态黑洞的瞬时辐出度．结果表明，动态黑洞的瞬时辐出度不仅与假定黑洞处于热力学平衡时的辐出度有关，还与黑洞的事件视界速度、事件视界

期刊

熵密度事件视界温度薄膜模型瞬时辐出度entropy density temperature of event horizon thin film m

F-35先进驾驶舱显示器的研制即将完成

期刊

F-35驾驶舱显示器洛克希德·马丁公司

一种基于交织重组和星座重组的Type-Ⅱ型混合ARQ方案

为提高系统的通过率及译码效率，高速可靠数据传输系统采用混合ARQ方案。本文提出了一种基于交织重组和星座重组的混合ARQ方案，分析了系统的通过率、误帧率及重传时延。通过仿真

期刊

正交频分复用交织重组星座重组ARQ通过率误帧率重传时延数字通信OFDM Data transmission Hybrid ARQ Thro

从马克思到邓小平的社会主义商品经济发展模式探析

社会主义国家能否发展商品经济，在马克思主义经济学说史上有过一个从否定到部分肯定再到肯定的认识发展过程。马克思、恩格斯预测社会主义是没有商品生产的社会。列宁认为从资

期刊

社会主义商品经济马克思列宁毛泽东邓小平socialism commodity economy Karl Marx Lenin Mao Zed

论毛泽东的对外开放思想

毛泽东同志是对外开放的倡导者和实践者，他在领导党和国家进行长期革命和建设的历史征程中，在对外开放问题上有着真知灼见：中国的发展离不开世界，要积极发展与外部世界的关系；要“

期刊

毛泽东对外开放诠释Mao Zedong opening up explanation

深刻理解和准确把握社会主义核心价值体系

社会主义核心价值体系,是由马克思主义指导思想、中国特色社会主义共同理想、以爱国主义为核心的民族精神和以改革创新为核心的时代精神、社会主义荣辱观四个方面的基本内容,

期刊

社会主义核心价值体系基本内容socialism core value system basic content

64DAPSK-OFDM与64QAM-OFDM系统性能比较

针对OFDM 系统中的MQAM和MDAPSK两种子载波高阶调制技术,介绍了64QAM和64DAPSK信号的比特软输出解调方法,比较了64DAPSK-OFDM和64QAM-OFDM系统的误码性能.仿真结果表明,在频

期刊

OFDM系统QAM子载波高阶调制频率选择性软输出误码性能仿真结果复杂度性能比较COFDM 64QAM 64DAPSK BER

充气天线结构技术概述

简要介绍了充气式可展开空间天线(以下简称充气天线)结构的关键技术,指出了充气天线的最新发展动向.

期刊

空间结构反射器天线可展开天线充气天线膜材料安装Space structureReflector antennaDeployable antenn

DSSS系统中基于Chirp-Fourier变换的扫频干扰抑制算法

提出一种直接序列扩频(DSSS)系统中基于Chirp-Fourier变换的扫频干扰(LFM)抑制算法,Chirp-Fourier变换可以有效地估计出加入噪声的LFM的初始频率和扫频率,从而可以设计出自适

期刊

扩频通信直接序列扩频Chirp-Fourier变换干扰抑制接收机算法Spread spectrum communication Direct seq

“三个代表”党之生命——苏联解体苏共垮台鉴

作为一个与美国抗衡半个多世纪的世界强国,苏联几乎在一夜之间轰然倒下,红旗落地,应该说无论在代表先进生产力的发展要求上,代表先进文化的前进方向上,还是在代表最广大人民

期刊

“三个代表”苏联剧变经验教训社会主义模式先进生产力先进文化Three Representatives' the drastic chang

关于满Steiner树问题的一个近似算法

与本文相关的学术论文